本文实例为大家分享了python实现双链表的具体代码，供大家参考，具体内容如下
实现双链表需要注意的地方
1、如何插入元素，考虑特殊情况：头节点位置，尾节点位置；一般情况：中间位置
2、如何删除元素，考虑特殊情况：头结点位置，尾节点位置；一般情况：中间位置
代码实现
1.构造节点的类和链表类
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class Node: def __init__(self, data): self.data = data self.next = None self.previous = Noneclass DoubleLinkList: '''双链表''' def __init__(self, node=None): self._head = node |
以下方法均在链表类中实现
2. 判断链表是否为空
|
1
2
|
def is_empty(self): return self._head is None |
3. 输出链表的长度
|
1
2
3
4
5
6
7
8
9
10
|
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 |
4. 遍历链表
|
1
2
3
4
5
6
|
def travel(self): current = self._head while current is not None: print("{0}".format(current.data), end=" ") current = current.next print("") |
5.头插法增加新元素
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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 |
6. 尾插法增加新元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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 |
7. 查找元素是否存在链表中
|
1
2
3
4
5
6
7
8
9
|
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 |
8. 在某个位置中插入元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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 |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# 换一个顺序也可以进行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 |
9. 删除元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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 |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
# 第二种写法 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 |
10. 演示
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
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() |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/CSDNwg/article/details/122492275
