线性表(双向链表(动图解析))

双向链表

双向链表或双面链表
每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

双向链表操作

判断链表是否为空、计算链表长度、遍历整个链表、查找指定元素的操作与单向链表相似

在头部添加元素

// An highlighted block
"""头部添加元素"""
    def add(self, item):
        node =  DoubleLinkList(item)
        node.next = self._head
        self._head = node
        node.next.prev=node

在尾部添加元素

使用cur游标找到尾部，然后对新的元素进行添加

// An highlighted block
 """尾部添加元素"""
    def append(self, item):
        node = DoubleLinkList(item)
        if self.is_empty():  # 先判断链表是否为空，若是空链表，则将_head指向新节点
            self._head = node  # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            cur = self._head
            while cur.next!= None:  # 判断下一个节点是否为None
                cur = cur.next
            cur.next = node
            node.prev=cur

指定位置添加元素

通过cur游标找到待添加元素的位置

// An highlighted block
"""在指定位置添加元素
    添加的元素是 (2,50)
    """
    def insert(self, pos, item):
        # 判断指定位置是进行头部添加还是尾部添加
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = DoubleLinkList(item)
            cur = self._head
            count = 0
            # 通过计数判断是否移动到指定位置
            while count < pos :
                count += 1
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next=node
            cur.prev=node

删除元素

// An highlighted block
   """删除一个节点"""
    def remove(self, item):
        # 若链表为空，则直接返回
        cur = self._head
        # 若头节点的元素就是要查找的元素item
        while cur != None:
            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
                break
            else:
                cur = cur.next

程序运行

// An highlighted block
class DoubleLinkList(object):
    """双链表"""
    def __init__(self,item=None,node=None):
        self.item = item
        self._head = node
        self.next = None

    '''判断链表是否为空'''
    def is_empty(self):
        return self._head == None

    """链表长度"""
    def length(self):
        cur = self._head  # cur初始时指向头节点
        count = 0
        while cur != None:  # 尾节点指向None，当未到达尾部时
            count=count+1
            cur=cur.next  # 将cur后移一个节点
        return count

    """遍历链表"""
    def travel(self):
        cur = self._head
        while cur != None:
            print(cur.item,end="\t")
            cur = cur.next
        print(end="\n")

    """尾部添加元素"""
    def append(self, item):
        node = DoubleLinkList(item)
        if self.is_empty():  # 先判断链表是否为空，若是空链表，则将_head指向新节点
            self._head = node  # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            cur = self._head
            while cur.next!= None:  # 判断下一个节点是否为None
                cur = cur.next
            cur.next = node
            node.prev=cur

    """头部添加元素"""
    def add(self, item):
        node =  DoubleLinkList(item)
        node.next = self._head
        self._head = node
        node.next.prev=node

     """在指定位置添加元素  添加的元素是 (2,50)"""
    def insert(self, pos, item):
        # 判断指定位置是进行头部添加还是尾部添加
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = DoubleLinkList(item)
            cur = self._head
            count = 0
            # 通过计数判断是否移动到指定位置
            while count < pos :
                count += 1
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next=node
            cur.prev=node


    """查找节点是否存在"""
    def search(self, item):
        cur = self._head
        while cur != None:
            if cur.item == item:
                print("True")
                return True
            else:
                cur = cur.next
        print("False")
        return False

    """删除一个节点"""
    def remove(self, item):
        # 若链表为空，则直接返回
        cur = self._head
        # 若头节点的元素就是要查找的元素item
        while cur != None:
            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
                break
            else:
                cur = cur.next



if __name__=="__main__":
    a=DoubleLinkList()
    print(a.is_empty())
    print(a.length())

    #在尾部增加元素
    a.append(1)
    print(a.is_empty())
    print(a.length())
    a.append(10)
    a.append(56)
    a.append(24)
    a.append(78)
    a.append(4)
    a.travel()
    #在头部增加元素
    a.add(20000)
    a.travel()
    # 在指定位置插入
    a.insert(3,50)
    a.travel()
    print(a.length())
    #删除元素
    a.remove(20000)
    a.travel()
    #查找元素
    a.search(50)
    a.search(10000)
    a.search(30000)