Python与数据结构[0] -> 链表/LinkedList[0] -> 单链表与带表头单链表的 Python 实现

单链表 / Linked List

单链表
带表头单链表

链表是一种基本的线性数据结构，在C语言中，这种数据结构通过指针实现，由于存储空间不要求连续性，因此插入和删除操作将变得十分快速。下面将利用Python来完成单链表的实现。

1 单链表

不带表头的单链表通常形式如下，

node_1 -> node_2 -> node_3 -> node_4

完整代码

Python与数据结构[0] -> 链表/LinkedList[0] -> 单链表与带表头单链表的 Python 实现

  1 class Node:
  2     def __init__(self, val=None, nxt=None):
  3         self.value = val
  4         self.next = nxt
  5 
  6     def __str__(self):
  7         return str(self.value)
  8 
  9 
 10 class LinkedList:
 11     """
 12     Linked list: 
 13             node_1 -> node_2 -> node_3 -> node_4  
 14     """
 15     def __init__(self, iterable=()):
 16         self.header = None
 17         if iterable:
 18             self.init(iterable)
 19 
 20     def __str__(self):
 21         def _traversal(self):
 22             node = self.header
 23             while node and node.next:
 24                 yield node
 25                 node = node.next
 26             yield node
 27         return '->'.join(map(lambda x: str(x), _traversal(self)))
 28 
 29     def init(self, iterable=()):
 30         # Note: use empty tuple rather than list to init iterable
 31         if not iterable:
 32             return
 33         self.header = Node(iterable[0])     # header value
 34         node = self.header
 35         for i in iterable[1:]:              # add all node
 36             node.next = Node(i)
 37             node = node.next
 38 
 39     def show(self):
 40         print(self)
 41 
 42     @property
 43     def length(self):
 44         if self.header is None:
 45             return 0
 46         node = self.header      # node pointer points to header
 47         i = 1
 48         while node.next:
 49             node = node.next    # node pointer move to next
 50             i += 1
 51         return i
 52 
 53     @property
 54     def is_empty(self):
 55         return self.header is None
 56         
 57     def clear(self):
 58         self.__init__()
 59         # self.header = None
 60 
 61     def append(self, item):
 62         self.insert(item, self.length)
 63 
 64     def find(self, item):
 65         node = self.header
 66         while node.next and node.value != item:
 67             node = node.next
 68         if node.value == item:
 69             return node
 70         return None
 71 
 72     def find_previous(self, item):
 73         node = self.header
 74         while node.next and node.next.value != item:
 75             node = node.next
 76         if node.next and node.next.value == item:
 77             return node
 78         return None
 79 
 80     def delete(self, item):
 81         '''
 82         node_1 -- X --> node_2 -----> node_3
 83             \                    /
 84              \                  /
 85               ------------------
 86         '''
 87         prev = self.find_previous(item)
 88         if prev:
 89             prev.next = prev.next.next
 90 
 91     def insert(self, item, index):
 92         '''
 93                 ----> node_2 ---
 94                /                \
 95               /                  \
 96         node_1 -------  X  ---------> node_3
 97 
 98         '''
 99         if abs(index) > self.length:
100             return
101         if index < 0:
102             self.insert(item, self.length+index+1)
103             return
104         elif index == 0:
105             self.insert(self.header.value, 1)
106             self.header.value = item
107             return
108         node = self.header
109         i = 0
110         while i < index-1:
111             node = node.next
112             i += 1
113         n = node.next 
114         node.next = Node(item, n)
115 
116 
117 def test(li):
118     print('Show linked list:')
119     li.show()
120 
121     print('\nInit linked list:')
122     li.init([1, 2, 3, 4, 5, 6, 'xd', 8, 9])
123     li.show()
124 
125     print('\nInsert element:')
126     li.insert('xxd', -3)
127     li.show()
128 
129     print('\nAppend element:')
130     li.append('10')
131     li.show()
132 
133     e = 'xd'
134     print('\nFind element:')
135     x = li.find(e)
136     print(x.value if x else x)
137     print('\nFind previous element:')
138     x = li.find_previous(e)
139     print(x.value if x else x)
140 
141     print('\nDelete element:')
142     li.delete('xd')
143     li.show()
144 
145     print('\nFind element not exist:')
146     x = li.find(e)
147     print(x.value if x else x)
148 
149     print('\nInsert element to header:')
150     li.insert('cc', 0)
151     li.show()
152  
153     print('\nClear linked list:')
154     li.clear()
155     li.show()
156 
157     print('\nCurrent length: %s' % li.length)
158     print('\nIs empty: %s' % li.is_empty)
159    
160 
161 if __name__ == '__main__':
162     test(LinkedList())

View Code

分段解释

首先，需要定义一个结点类（在C语言中则使用结构体进行定义），其中包括两个基本属性，当前值和下个结点。由于Python中无法使用类似C语言中的指针，因此只能通过变量的引用来实现类似指针操作的功能。为了更好的显示结点，这里重载了结点的内置函数__str__。

1 class Node:
2     def __init__(self, val=None, nxt=None):
3         self.value = val
4         self.next = nxt
5 
6     def __str__(self):
7         return str(self.value)

接着，我们需要。定义一个链表类，并利用前面的结点来构建这个链表。链表类中包含了一个头结点属性，在初始化函数中，首先将头结点赋值None，类似于在C语言中将头结点指针指向NULL。初始化方法中定义了一个默认参数，使得链表可以在实例化的时候利用传入的可迭代对象进行链表生成。

1 class LinkedList:
2     """
3     Linked list:
4             node_1 -> node_2 -> node_3 -> node_4
5     """
6     def __init__(self, iterable=()):
7         self.header = None
8         if iterable:
9             self.init(iterable)

重载链表的__str__方法，在显示链表的时候会对链表进行遍历，然后以更加清晰的方式显示在输出终端上。

1     def __str__(self):
2         def _traversal(self):
3             node = self.header
4             while node and node.next:
5                 yield node
6                 node = node.next
7             yield node
8         return '->'.join(map(lambda x: str(x), _traversal(self)))

定义链表的生成函数，函数中接收可迭代对象并生成新的链表。注意这里最好使用不可变的元组而不是可变的列表。

在生成时，首先将第一个元素作为头结点，然后依次将每个结点的next属性引用指向下一个结点。

1     def init(self, iterable=()):
2         # Note: use empty tuple rather than list to init iterable
3         if not iterable:
4             return
5         self.header = Node(iterable[0])     # header value
6         node = self.header
7         for i in iterable[1:]:              # add all node
8             node.next = Node(i)
9             node = node.next

链表的show方法，由于已经重载了__str__方法，这里只需要print自身即可。

1     def show(self):
2         print(self)

链表的length属性方法，用于返回链表的长度，利用装饰器定义成属性方法，调用时遍历链表计算长度最后返回即可。

 1     @property
 2     def length(self):
 3         if self.header is None:
 4             return 0
 5         node = self.header      # node pointer points to header
 6         i = 1
 7         while node.next:
 8             node = node.next    # node pointer move to next
 9             i += 1
10         return i

链表的is_empty属性方法，用于检测链表是否为空，只需要查看头结点是否为None即可。

1     @property
2     def is_empty(self):
3         return self.header is None

链表的clear方法，用于清空链表，可以选择直接初始化链表或将链表的头结点指向None。

1     def clear(self):
2         self.__init__()
3         # self.header = None

链表的append方法，用于在链表尾部添加一个元素结点，这里只要直接调用后面的insert方法并插入到链表长度的那个位置即可。

1     def append(self, item):
2         self.insert(item, self.length)

链表的find方法，用于在链表中查找并返回某个结点，查找时会从链表的头部开始，遍历查找，直到找到查找的值或遇到None，这里的find方法有两点需要注意：

查找是依据元素的值进行查找，返回找到的第一个结点；
这里的查找方法如果遇到有环链表将无法自行检测退出

最后返回查找到的结点或None。

1     def find(self, item):
2         node = self.header
3         while node.next and node.value != item:
4             node = node.next
5         if node.value == item:
6             return node
7         return None

find_previous与find类似，返回查找结点的前一个结点。

1     def find_previous(self, item):
2         node = self.header
3         while node.next and node.next.value != item:
4             node = node.next
5         if node.next and node.next.value == item:
6             return node
7         return None

delete方法用于删除结点，基本思路在于，找到需要删除结点node_2的前一个结点node_1，将前一个结点node_1的next指针指向删除结点的下一个结点node_3，从而惰性删除了这个结点。

查找前一个结点可以使用前面定义的find_previous方法。

 1     def delete(self, item):
 2         '''
 3         node_1 -- X --> node_2 -----> node_3
 4             \                    /
 5              \                  /
 6               ------------------
 7         '''
 8         prev = self.find_previous(item)
 9         if prev:
10             prev.next = prev.next.next

insert方法用于向链表中插入一个结点，

基本思路在于，找到需要插入的位置前后的两个结点node_1和node_3，将node_1.next指向需要插入的结点node_2，再将node_2.next指向node_3，便完成了插入操作。

若插入的位置为头结点之前，则会替换原来的头结点为新插入的结点。

同时，这里的插入函数还支持index为负数的情况，类似于列表的负数索引。

 1     def insert(self, item, index):
 2         '''
 3                 ----> node_2 ---
 4                /                \
 5               /                  \
 6         node_1 -------  X  ---------> node_3
 7 
 8         '''
 9         if abs(index) > self.length:
10             return
11         if index < 0:
12             self.insert(item, self.length+index+1)
13             return
14         elif index == 0:
15             self.insert(self.header.value, 1)
16             self.header.value = item
17             return
18         node = self.header
19         i = 0
20         while i < index-1:
21             node = node.next
22             i += 1
23         n = node.next 
24         node.next = Node(item, n)

最后，定义一个测试函数用于测试链表的各种操作。

开始时显示空表

1 def test(li):
2     print('Show linked list:')
3     li.show()

得到结果

Show linked list:
None

接着初始化链表元素

1     print('\nInit linked list:')
2     li.init([1, 2, 3, 4, 5, 6, 'xd', 8, 9])
3     li.show()

得到结果

Init linked list:
1->2->3->4->5->6->xd->8->9

再向链表中插入元素

1     print('\nInsert element:')
2     li.insert('xxd', -3)
3     li.show()

得到结果

Insert element:
1->2->3->4->5->6->xd->xxd->8->9

向链表末尾添加元素

1     print('\nAppend element:')
2     li.append('10')
3     li.show()

得到结果

Append element:
1->2->3->4->5->6->xd->xxd->8->9->10

查找元素

1     e = 'xd'
2     print('\nFind element:')
3     x = li.find(e)
4     print(x.value if x else x)
5     print('\nFind previous element:')
6     x = li.find_previous(e)
7     print(x.value if x else x)

得到结果

Find element:
xd

Find previous element:
6

删除元素

1     print('\nDelete element:')
2     li.delete('xd')
3     li.show()

得到结果

Delete element:
1->2->3->4->5->6->xxd->8->9->10

查找不存在的元素

1     print('\nFind element not exist:')
2     x = li.find(e)
3     print(x.value if x else x)

得到结果

Find element not exist:
None

替换头结点

1     print('\nInsert element to header:')
2     li.insert('cc', 0)
3     li.show()

得到结果

Insert element to header:
cc->1->2->3->4->5->6->xxd->8->9->10

清空链表并查看链表信息

1     print('\nClear linked list:')
2     li.clear()
3     li.show()
4 
5     print('\nCurrent length: %s' % li.length)
6     print('\nIs empty: %s' % li.is_empty)

得到结果

Clear linked list:
None

Current length: 0

Is empty: True

2 带表头单链表

这种单链表带有一个标志结点，通常被称为表头或哑结点，表头通常位于位置0处，通常不会被改变。

Linked list with dummy header node:
       Header -> node_1 -> node_2 -> node_3

带表头的单链表在实现时与不带表头的单链表类似，因此可以继承前面的单链表类来派生出一个带表头单链表类，其中需要进行修改和重载的方法主要有生成链表、判断链表为空和插入链表这几个方法。

 1 from linked_list import Node, LinkedList, test
 2 
 3 
 4 class LinkedListDummyHeader(LinkedList):
 5     """
 6     Linked list with dummy header node:
 7             Header -> node_1 -> node_2 -> node_3
 8     """
 9     def __init__(self, iterable=()):
10         self.header = Node('Header', None)
11         if iterable:
12             self.init(iterable)
13 
14     def init(self, iterable=()):
15         if not iterable:
16             return
17         node = self.header
18         for i in iterable:
19             node.next = Node(i)
20             node = node.next
21 
22     @property
23     def is_empty(self):
24         return self.header.next is None
25         # if self.length == 1:
26         #     return True
27         # return False
28 
29     def insert(self, item, index):
30         if index == 0:
31             return
32         super(LinkedListDummyHeader, self).insert(item, index)
33 
34 if __name__ == '__main__':
35     test(LinkedListDummyHeader())

__init__方法：

初始化时头结点不再指向None，而是指向表头。

init方法：

由于有表头的存在，因此创建初始链表的方法首先需要建立一个表头，再将所有元素依次加入链表中。

is_empty方法：

由于表头的存在，此时判断是否为空则可以根据表头指向结点是否为空，或链表长度是否为1来进行。

insert方法：

此处需要修改的地方在于当插入点为表头时，则应该直接返回或引发异常，无法修改表头。

最后利用单链表的测试函数进行测试得到结果

Show linked list:
Header

Init linked list:
Header->1->2->3->4->5->6->xd->8->9

Insert element:
Header->1->2->3->4->5->6->xd->xxd->8->9

Append element:
Header->1->2->3->4->5->6->xd->xxd->8->9->10

Find element:
xd

Find previous element:
6

Delete element:
Header->1->2->3->4->5->6->xxd->8->9->10

Find element not exist:
None

Insert element to header:
Header->1->2->3->4->5->6->xxd->8->9->10

Clear linked list:
Header

Current length: 1

Is empty: True

秒客网

Python与数据结构[0] -> 链表/LinkedList[0] -> 单链表与带表头单链表的 Python 实现

相关文章