python实现双链表

# 双链表
class Node(object):
    # 初始化双向链表节点
    def __init__(self,item):
        self.item=item
        self.next=None
        self.pre=None
class DoubleLinkList(object):
    # 1、初始化双链表
    def __init__(self):
        self._head=None
    # 2、判断双链表是否为空
    def is_empty(self):
        return self._head == None
    # 3、获取双链表的长度
    def get_length(self):
        cur=self._head
        count =0
        while cur !=None:
            # 返回链表的长度
            count=count+1
            cur=cur.next
        return count
    # 4、遍历双链表
    def travel(self):
        cur =self._head
        while cur !=None:
            print(cur.item)
            cur=cur.next
        print("")
    # 5、头部添加元素
    def add(self,item):
        node=Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head=node
        else:
            # 将node的next指向_head的头节点
            node.next=self._head
            # 将_head的头节点的prev指向node
            self._head.pre=node
            # 将_head 指向node
            self._head=node
    #6、尾部添加元素
    def append(self, value):
        node = Node(value)
        cur = self._head
        if self.is_empty():
            self._head = Node
            return
        while cur.next:
            cur = cur.next
        cur.next = node
        node.prev = cur
    # 7、指定位置添加元素
    def insert(self, pos, value):
        if pos <= 0:
            self.add(value)
        elif pos > self.get_length() - 1:
            self.append(value)
        else:
            # 单向链表中为了在特定位置插入，要先在链表中找到待插入位置和其前一个位置
            # 双向链表中就不需要两个游标了（当然单向链表中一个游标也是可以只找前一个位置）
            node = Node(value)
            count = 0
            cur = self._head
            while count < pos - 1:
                count += 1
                cur = cur.next
            # 此时的游标指向pos的前一个位置
            # 这里的相互指向需尤为注意，有多种实现，需细细分析
            node.next = cur.next
            cur.next.prev = node
            node.prev = cur
            cur.next = node
    #8、搜索指定元素
    def search(self, item):
        cur = self._head
        while cur:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False
    # 9、删除指定的元素
    def remove(self, item):
        if self.is_empty():
            return
        cur = self._head
        while cur:
            if cur.item == item:
                if cur == self._head:
                    self._head = cur.next
                    # 处理链表只有一个节点的特殊情况
                    if cur.next:
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    # 处理待删除节点是最后一个情况
                    if cur.next:
                        cur.next.prev = cur.prev
                return
            else:
                cur = cur.next
# 测试
if __name__ == "__main__":
    lst = DoubleLinkList()
    print(lst.is_empty())
    print(lst.get_length())
    lst.add(1)
    lst.add(2)
    lst.travel()
    lst.append(3)
    lst.travel()
    lst.insert(2,100)
    lst.travel()
    lst.search(100)
    lst.remove(100)
    lst.travel()

C:\Anaconda3\python.exe "C:\Program Files\JetBrains\PyCharm 2019.1.1\helpers\pydev\pydevconsole.py" --mode=client --port=59682
import sys; print(‘Python %s on %s‘ % (sys.version, sys.platform))
sys.path.extend([‘C:\\app\\PycharmProjects‘, ‘C:/app/PycharmProjects‘])
Python 3.7.6 (default, Jan  8 2020, 20:23:39) [MSC v.1916 64 bit (AMD64)]
Type ‘copyright‘, ‘credits‘ or ‘license‘ for more information
IPython 7.12.0 -- An enhanced Interactive Python. Type ‘?‘ for help.
PyDev console: using IPython 7.12.0
Python 3.7.6 (default, Jan  8 2020, 20:23:39) [MSC v.1916 64 bit (AMD64)] on win32
runfile(‘C:/app/PycharmProjects/DataStructure/LinkedList/double_linked_list.py‘, wdir=‘C:/app/PycharmProjects/DataStructure/LinkedList‘)
True
0
2
1
2
1
3
2
1
100
3
2
1
3