双向链表

灰太狼 2022-12-21 04:54 195阅读 0赞

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70]

## 操作 ##

*  is\_empty() 链表是否为空
 *  length() 链表长度
 *  travel() 遍历链表
 *  add(item) 链表头部添加
 *  append(item) 链表尾部添加
 *  insert(pos, item) 指定位置添加
 *  remove(item) 删除节点
 *  search(item) 查找节点是否存在

## 实现 ##

class Node(object):
        """双向链表节点"""
        def __init__(self, item):
            self.item = item
            self.next = None
            self.prev = None
    
    
    class DLinkList(object):
        """双向链表"""
        def __init__(self):
            self._head = None
    
        def is_empty(self):
            """判断链表是否为空"""
            return self._head == None
    
        def length(self):
            """返回链表的长度"""
            cur = self._head
            count = 0
            while cur != None:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            """遍历链表"""
            cur = self._head
            while cur != None:
                print cur.item,
                cur = cur.next
            print ""
    
        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.prev = node
                # 将_head 指向node
                self._head = node
    
        def append(self, item):
            """尾部插入元素"""
            node = Node(item)
            if self.is_empty():
                # 如果是空链表，将_head指向node
                self._head = node
            else:
                # 移动到链表尾部
                cur = self._head
                while cur.next != None:
                    cur = cur.next
                # 将尾节点cur的next指向node
                cur.next = node
                # 将node的prev指向cur
                node.prev = cur
    
    
    
        def search(self, item):
            """查找元素是否存在"""
            cur = self._head
            while cur != None:
                if cur.item == item:
                    return True
                cur = cur.next
            return False

指定位置插入节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 1]

def insert(self, pos, item):
            """在指定位置添加节点"""
            if pos <= 0:
                self.add(item)
            elif pos > (self.length()-1):
                self.append(item)
            else:
                node = Node(item)
                cur = self._head
                count = 0
                # 移动到指定位置的前一个位置
                while count < (pos-1):
                    count += 1
                    cur = cur.next
                # 将node的prev指向cur
                node.prev = cur
                # 将node的next指向cur的下一个节点
                node.next = cur.next
                # 将cur的下一个节点的prev指向node
                cur.next.prev = node
                # 将cur的next指向node
                cur.next = node

删除元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 2]

def remove(self, item):
            """删除元素"""
            if self.is_empty():
                return
            else:
                cur = self._head
                if cur.item == item:
                    # 如果首节点的元素即是要删除的元素
                    if cur.next == None:
                        # 如果链表只有这一个节点
                        self._head = None
                    else:
                        # 将第二个节点的prev设置为None
                        cur.next.prev = None
                        # 将_head指向第二个节点
                        self._head = cur.next
                    return
                while cur != None:
                    if cur.item == item:
                        # 将cur的前一个节点的next指向cur的后一个节点
                        cur.prev.next = cur.next
                        # 将cur的后一个节点的prev指向cur的前一个节点
                        cur.next.prev = cur.prev
                        break
                    cur = cur.next

测试

if __name__ == "__main__":
        ll = DLinkList()
        ll.add(1)
        ll.add(2)
        ll.append(3)
        ll.insert(2, 4)
        ll.insert(4, 5)
        ll.insert(0, 6)
        print "length:",ll.length()
        ll.travel()
        print ll.search(3)
        print ll.search(4)
        ll.remove(1)
        print "length:",ll.length()
        ll.travel()

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70]: /images/20221120/77616a06508a46989b67556248bb8ce1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190820175340922.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190820175404247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIwMDQyOTM1,size_16,color_FFFFFF,t_70