python如何实现双链表

本篇内容介绍了“python如何实现双链表”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

实现双链表需要注意的地方

如何插入元素，考虑特殊情况：头节点位置，尾节点位置；一般情况：中间位置
2、如何删除元素，考虑特殊情况：头结点位置，尾节点位置；一般情况：中间位置

代码实现

构造节点的类和链表类

class node:    def __init__(self, data):        self.data = data        self.next = None        self.previous = Noneclass DoubleLinkList:    '''双链表'''    def __init__(self, node=None):        self._head = node

以下方法均在链表类中实现

判断链表是否为空

def is_empty(self):        return self._head is None

输出链表的长度

def length(self):        count = 0        if self.is_empty():            return count        else:            current = self._head            while current is not None:                count += 1                current = current.next        return count

遍历链表

def travel(self):        current = self._head        while current is not None:            print("{0}".fORMat(current.data), end=" ")            current = current.next        print("")

头插法增加新元素

def add(self, item):        node = Node(item)        # 如果链表为空，让头指针指向当前节点        if self.is_empty():            self._head = node        # 注意插入的顺序，        else:            node.next = self._head            self._head.previous = node            self._head = node

尾插法增加新元素

def append(self, item):        node = Node(item)        # 如果链表为空，则直接让头指针指向该节点        if self.is_empty():            self._head = node        # 需要找到尾节点，然后让尾节点的与新的节点进行连接        else:            current = self._head            while current.next is not None:                current = current.next            current.next = node            node.previous = current

查找元素是否存在链表中

def search(self, item):        current = self._head        found = False        while current is not None and not found:            if current.data == item:                found = True            else:                current = current.next        return found

在某个位置中插入元素

def insert(self, item, pos):        # 特殊位置，在第一个位置的时候，头插法        if pos <= 0:            self.add(item)        # 在尾部的时候，使用尾插法        elif pos > self.length() - 1:            self.append(item)        # 中间位置        else:            node = Node(item)            current = self._head            count = 0            while count < pos - 1:                current = current.next                count += 1            # 找到了要插入位置的前驱之后，进行如下操作            node.previous = current            node.next = current.next            current.next.previous = node            current.next = node

 # 换一个顺序也可以进行def insert2(self, item, pos):        if pos <= 0:            self.add(item)        elif pos > self.length() - 1:            self.append(item)        else:            node = Node(item)            current = self._head            count = 0            while count < pos:                current = current.next                count += 1            node.next = current            node.previous = current.previous            current.previous.next = node            current.previous = node

删除元素

def remove(self, item):        current = self._head        if self.is_empty():            return        elif current.data == item:            # 第一个节点就是目标节点，那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点            current.next.previous = None            self._head = current.next        else:            # 找到要删除的元素节点            while current is not None and current.data != item:                current = current.next            if current is None:                print("not found {0}".format(item))            # 如果尾节点是目标节点，让前驱节点指向None            elif current.next is None:                current.previous.next = None            # 中间位置，因为是双链表，可以用前驱指针操作            else:                current.previous.next = current.next                current.next.previous = current.previous

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

演示

my_list = DoubleLinkList()print("add操作")my_list.add(98)my_list.add(99)my_list.add(100)my_list.travel()print("{:#^50}".format(""))print("append操作")my_list.append(86)my_list.append(85)my_list.append(88)my_list.travel()print("{:#^50}".format(""))print("insert2操作")my_list.insert2(66, 3)my_list.insert2(77, 0)my_list.insert2(55, 10)my_list.travel()print("{:#^50}".format(""))print("insert操作")my_list.insert(90, 4)my_list.insert(123, 5)my_list.travel()print("{:#^50}".format(""))print("search操作")print(my_list.search(100))print(my_list.search(1998))print("{:#^50}".format(""))print("remove操作")my_list.remove(56)my_list.remove(123)my_list.remove(77)my_list.remove(55)my_list.travel()print("{:#^50}".format(""))print("remove2操作")my_list.travel()my_list.remove2(100)my_list.remove2(99)my_list.remove2(98)my_list.travel()

“Python如何实现双链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！