双向链表

class Node(object):
    def __init__(self, item, prev, next):
        self.item = item
        self.prev = prev
        self.next = next


class DoubleLink(object):
    def __init__(self, init_list):
        self._link = None
        self._init_link(init_list)

    def _init_link(self, init_list):
        init_list.reverse()
        prev = None
        for item in init_list:
            self._link = Node(item, None, self._link)
            if prev is not None:
                self._link.next.prev = self._link
            prev = self._link

    @property
    def list(self):
        res = []
        link = self._link
        while link:
            try:
                _prev = link.prev.item
            except:
                _prev = ''
            try:
                _next = link.next.item
            except:
                _next = ''
            t = (_prev, link.item, _next)
            res.append(t)
            link = link.next
        return res

    @property
    def length(self):
        return len(self.list)

    def append(self, item):
        """
        向链表尾部添加一个元素
        :param item:
        :return:
        """
        link = self._link
        while link:
            if link.next is None:
                link.next = Node(item, link, None)
                break
            link = link.next

    def unshift(self, item):
        """
        向链表头部添加一个元素
        :param item:
        :return:
        """
        self._link = Node(item, None, self._link)
        self._link.next.prev = self._link

    def insert(self, item, index):
        """
        向index位置插入一个元素item
        index从0开始计数
        :param item:
        :param index:
        :return:
        """
        length = self.length
        if index > length - 1:
            raise Exception('越界')
        if index == 0:
            self.unshift(item)
        elif index == self.length - 1:
            self.append(item)
        else:
            link = self._link
            _index = 0
            while link:
                if _index == index:
                    link.prev.next = Node(item, link.prev, link)
                    link.prev = link.prev.next
                    break
                link = link.next
                _index += 1

    def get_node(self, index):
        """
        根据下标取得某个元素对象
        :param index:
        :return:
        """
        link = self._link
        _index = 0
        while link:
            if _index == index:
                return link
            link = link.next
            _index += 1

    def get_index(self, item):
        """
        取得某个元素的下标
        :param item:
        :return:
        """
        link = self._link
        _index = 0
        while link:
            if link.item == item:
                return _index
            link = link.next
            _index += 1

    def pop(self):
        """
        删除链表中最后一个元素
        :return:
        """
        link = self._link
        while link:
            if link.next is None:
                link.prev.next = None
                break
            link = link.next

    def shift(self):
        """
        删除链表中第一个元素
        :return:
        """
        self._link = self._link.next
        self._link.prev = None

    def delete(self, item):
        """
        删除链表中某个元素
        :param item:
        :return:
        """
        length = self.length
        link = self._link
        _index = 0
        while link:
            if link.item == item:
                if _index == 0:
                    self.shift()
                elif _index == length - 1:
                    self.pop()
                else:
                    link.prev.next = link.next
                    link.next.prev = link.prev
                break
            link = link.next
            _index += 1


if __name__ == '__main__':
    link = DoubleLink(['zhangbo', 'liudong', 'zhuxaing'])
    print(link.list)
    link.insert('wuxiaokang', 2)
    print(link.list)
    # print(link.get_node(2).item)
    # print(link.get_index('wuxiaokang'))
    link.delete('zhuxaing')
    print(link.list)