算法—详细讲解双向链表的实现（python）

双向链表

双向链表的实现

一、往链表的头部增加一个节点

    # 新建一个节点
    node = Node(data)
    # 判断链表是否为空
    if self.is_empty():
        self.head = node
    else:
        # 让链表中原本的头节点的prev指向新的节点
        self.head.prev = node
        # 先让node指向当前链表中的头节点
        node.next = self.head
        # 再让链表的head指向当前node节点
        self.head = node
    # 添加节点之后，链表的长度加1
    self._length += 1

二、链表尾部添加一个节点

    node = Node(data)
    if self.head:
        cur = self.head  # 将头节点的地址赋给了变量cur
        while cur.next:
            cur = cur.next
        node.prev = cur  # 让node的prev指针域去指向原本的尾节点
        cur.next = node  # 让原本的尾节点的next指向新建的节点
    else:
        self.head = node
    # 让当前的尾节点的指针指向新建的节点node
    # 链表的长度加1
    self._length += 1

三、往链表指定位置插入一个节点，值为data

       1新建一个节点
        node = Node(data)
        # 2找到链表中索引为pos-1的节点
        cur = self.head
        while pos - 1:
            cur = cur.next
            pos -= 1
        # 到这里之后，cur指向的是索引为pos-1的节点
        # 让node的prev指向索引为pos-1的节点
        node.prev = cur
        # 让node的next指向索引为pos的节点
        cur.next.prev = node
        # 让索引为pos的节点指向新建的节点
        node.next = cur.next
        # 4让索引为pos-1的节点的next指向node
        cur.next = node
        # 5链表的长度加1
        self._length += 1

四、删除链表中第一个值为data的节点

	cur = self.head
    while cur:
        if cur.data == data:
            if cur == self.head:
                self.head = cur.next
            else:
                cur.prev.next = cur.next
            if cur.next:
                cur.next.prev=cur.prev
            self._length -= 1
            return 0
        cur = cur.next
    return -1

五、修改链表中指定位置节点的值

    if 0 < pos < self._length:
        cur = self.head
        while pos:
            cur = cur.next
            pos -= 1
        cur.data = data
    else:
        print('输入的范围不符合要求')

六、查找链表中是否有节点的值为data

cur=self.head
while  cur:
		if cur.data==data:
				return 1
		else:
				cur=cur.next
return -1

代码块：

class Node:

    def __init__(self, data, _prev=None, _next=None):
        self.prev = _prev  # 指针域，指向当前节点的前一个节点
        self.data = data  # 数据域
        self.next = _next  # 指针域 指向当前节点的后一个节点


class DoubleLinkList:

    def __init__(self):
        self.head = None  # 链表的的头节点
        self._length = 0  # 链表的长度，链表的元素个数

    def is_empty(self):
        # 判断链表的是否为空
        return self._length == 0

    def length(self):
        # 返回链表的长度
        return self._length

    def nodes_list(self):
        # 返回链表中的所有节点的值组成的列表
        res = []
        cur = self.head
        while cur:
            res.append(cur.data)
            cur = cur.next
        return res

    def add(self, data):
        # 往链表的头部添加一个节点，值为data
        # 新建一个节点
        node = Node(data)
        # 判断链表是否为空
        if self.is_empty():
            self.head = node
        else:
            # 让链表中原本的头节点的prev指向新的节点
            self.head.prev = node
            # 先让node指向当前链表中的头节点
            node.next = self.head
            # 再让链表的head指向当前node节点
            self.head = node
        # 添加节点之后，链表的长度加1
        self._length += 1

    def append(self, data):
        # 往链表的尾部添加一个节点，值为data
        # 新建一个节点node，值为data
        node = Node(data)
        if self.head:
            cur = self.head  # 将头节点的地址赋给了变量cur
            while cur.next:
                cur = cur.next
            node.prev = cur  # 让node的prev指针域去指向原本的尾节点
            cur.next = node  # 让原本的尾节点的next指向新建的节点
        else:
            self.head = node
        # 让当前的尾节点的指针指向新建的节点node
        # 链表的长度加1
        self._length += 1

    def insert(self, pos, data):
        # 往链表的指定位置插入一个节点，值为data
        if pos <= 0:
            self.add(data)
        elif pos > self._length:
            self.append(data)
        else:
            # 1新建一个节点
            node = Node(data)
            # 2找到链表中索引为pos-1的节点
            cur = self.head
            while pos - 1:
                cur = cur.next
                pos -= 1
            # 到这里之后，cur指向的是索引为pos-1的节点
            # 让node的prev指向索引为pos-1的节点
            node.prev = cur
            # 让node的next指向索引为pos的节点
            cur.next.prev = node
            # 让索引为pos的节点指向新建的节点
            node.next = cur.next
            # 4让索引为pos-1的节点的next指向node
            cur.next = node
            # 5链表的长度加1
            self._length += 1

    def remove(self, data):
        # 删除链表中第一个值为data的节点
        cur = self.head
        while cur:
            if cur.data == data:
                if cur == self.head:
                    self.head = cur.next
                else:
                    cur.prev.next = cur.next
                if cur.next:
                    cur.next.prev=cur.prev
                self._length -= 1
                return 0
            cur = cur.next
        return -1

    def modify(self, pos, data):
        # 修改链表中指定位置节点的值
        if 0 < pos < self._length:
            cur = self.head
            while pos:
                cur = cur.next
                pos -= 1
            cur.data = data
        else:
            print('输入的范围不符合要求')

    def search(self, data):
        # 查找链表中是否有节点的值为data
        cur = self.head
        while cur:
            if cur.data == data:
                return True
            cur = cur.next
        return False


if __name__ == '__main__':
    l1 = DoubleLinkList()  # 新建一个链表类
    print(l1.head, l1.length())
    l1.add(1)
    print(l1.nodes_list())
    l1.append(2)
    print(l1.nodes_list())
    l1.append(3)
    print(l1.nodes_list())
    l1.insert(1, 8)
    print(l1.nodes_list())
    l1.remove(2)
    print(l1.nodes_list())
    l1.remove(1)
    print(l1.nodes_list())
    l1.modify(1,7)
    print(l1.nodes_list())
    print(l1.search(7))