Python 数据结构之链表 —— （一）功能实现

zltzlt

来源于 CSDN，有更改

Python 数据结构之链表 —— （一）功能实现

链表（Linked list）是一种常见的基础数据结构，是一种线性表。

但是它并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针 (Pointer)。

由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多。

但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。

链表的特点：使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

基本操作：包括创建链表（初始化）、获取长度、插入、查找、删除、遍历，以及略复杂的链表逆序和结点交换。

下面将这些操作一一实现并作出解释。

代码如下：

1. class ListNode(object):
   
2.     def __init__(self, data, p=None):
   
3.         self.data = data
   
4.         self.next = p
   
5. 
   
6. 
   
7. class Linklist(object):
   
8.     def __init__(self):
   
9.         self.head = None
   
10. 
    
11.     def set(self):  # 初始建立
    
12.         print('input:')
    
13.         data = input()
    
14.         if data != "":
    
15.             self.head = ListNode(int(data))
    
16.             p = self.head
    
17.         else:
    
18.             print('over!')
    
19.             return
    
20.         while 1:
    
21.             data = input()
    
22.             if data != "":
    
23.                 p.next = ListNode(int(data))
    
24.                 p = p.next
    
25.             else:
    
26.                 print('over!')
    
27.                 break
    
28. 
    
29.     @property
    
30.     def show(self):  # 遍历链表
    
31.         print('链表元素如下：')
    
32.         p = self.head
    
33.         if p is None:
    
34.             print('Empty!')
    
35.             return
    
36.         while p:
    
37.             print(p.data, end=',')
    
38.             p = p.next
    
39.         print('over!')
    
40. 
    
41.     @property
    
42.     def isempty(self):  # 判断是否空
    
43.         p = self.head
    
44.         if p is None:
    
45.             return True
    
46.         else:
    
47.             return False
    
48. 
    
49.     @property
    
50.     def length(self):  # 获取长度
    
51.         p = self.head
    
52.         n = 0
    
53.         while p:
    
54.             n += 1
    
55.             p = p.next
    
56.         return n
    
57. 
    
58.     def insert(self, data, pos):  # 数据插入
    
59.         if self.isempty and pos != 1:
    
60.             raise Exception('wrong position!')
    
61.         p = self.head
    
62.         if pos == 1:
    
63.             self.head = ListNode(data)
    
64.             self.head.next = p
    
65.         n = 2
    
66.         while n < pos and p.next is not None:
    
67.             p = p.next
    
68.             n += 1
    
69.         if n == pos:
    
70.             tmp = p.next
    
71.             p.next = ListNode(data)
    
72.             p = p.next
    
73.             p.next = tmp
    
74.         elif n < pos:
    
75.             raise Exception('wrong position!')
    
76. 
    
77.     def delete(self, pos):  # 删除操作
    
78.         p = self.head
    
79.         # 假设位置信息有效
    
80.         if pos == 1:
    
81.             return self.head.next
    
82.         for i in range(pos - 2):
    
83.             p = p.next
    
84.         p.next = p.next.next

复制代码

以上是一些基本操作，注意以下几点：

1. 基本操作的关键是学会链表的遍历和定位，每个操作参数表如何、返回值如何都可根据实际问题相应改变，做题时一般不是作为一个链表 class 的方法。
2. next 结点默认为 None，遍历时 while p 即可，比较方便；
3. 最重要一点是，大多数问题，都需要单独、特别处理头结点，需要养成良好习惯。一般题目给出的参数都是 head 即链表的头，先判断 head is None 是很常见的，再进行后续处理。

下面是链表的逆序问题，参考博客单链表反转 Python 实现。

一个循环方法，一个递归方法，关键是理解其原理，然后可以很自然得写出来，链表的逆转是很重要的基本功。

下图是对循环方法的图解，我认为理解并熟练运用这一方法即可~

                               
登录/注册后可看大图

1. # 循环方法
   
2. def reverse(head):
   
3.     if head is None or head.next is None:
   
4.         return head
   
5.     pre = None
   
6.     cur = head
   
7.     h = head
   
8.     while cur:
   
9.         h = cur
   
10.         tmp = cur.next
    
11.         cur.next = pre
    
12.         pre = cur
    
13.         cur = tmp
    
14.     return h
    
15. 
    
16. 
    
17. def recurse(head, newhead):        # 递归方法，head 为原链表的头结点，newhead 为反转后链表的头结点
    
18.     if head is None:              # 使用时需先初始化 newhead
    
19.         return
    
20.     if head.next is None:
    
21.         newhead = head
    
22.     else :
    
23.         newhead = recurse(head.next,newhead)
    
24.         head.next.next = head
    
25.         head.next = None
    
26.     return newhead

复制代码

最为复杂的是链表结点的交换问题，但是原理并不复杂，由于面对链表头这玩意，在 head 前加一个结点通常比较舒服。

其次是交换时定位到两个结点前一个的位置即可。

最后注意的是交换两个相邻结点的情况要特殊处理。

代码如下，是交换第 m 个和第 n 个结点，亲测可用，供大家交流学习。

1. def swap(head, m, n):
   
2.     # 认为 m, n 有效
   
3.     newhead = ListNode(-1)  # 0 结点
   
4.     newhead.next = head
   
5.     p = newhead
   
6.     for i in range(m - 1):  # 定位到 m-1 处
   
7.         p = p.next
   
8.     if m + 1 == n:  # 二者相邻时
   
9.         q = p.next
   
10.         tmp = q.next.next
    
11.         p.next = q.next
    
12.         p.next.next = q
    
13.         q.next = tmp
    
14.         return newhead.next
    
15.     else:
    
16.         q = p
    
17.         for i in range(n - m):  # 一般情况时，定位到 n-1 处
    
18.             q = q.next
    
19.         tmp = q.next.next
    
20.         nodem = p.next
    
21.         p.next = q.next
    
22.         p.next.next = nodem.next
    
23.         q.next = nodem
    
24.         q.next.next = tmp
    
25.         return newhead.next

复制代码

这些是单链表，还有一种双向链表。

优点是方便我们前向寻找结点，使一些问题更简单；

而缺点是当我们熟悉了单链表的那一套理论后，很可能不会使用这玩意儿。

双向链表占用更多空间，在删除、插入、逆序等各种操作时都会额外增加问题。

如果遇到这方面的问题还是要认真研究一番。

1. class LinkedList:
   
2.     def __init__(self, value):
   
3.         self.value = value
   
4.         # 前结点
   
5.         self.before = None
   
6.         # 后结点
   
7.         self.behind = None

复制代码

这就是链表的基本理论和方法，需要亲自实验一番才好~

yexing

前排支持
可以在鱼c学数据结构了

zltzlt

yexing 发表于 2020-3-6 20:35
前排支持
可以在鱼c学数据结构了

还有算法呢~

https://fishc.com.cn/forum.php?m ... =view&ctid=1661

yexing

zltzlt 发表于 2020-3-6 20:49
还有算法呢~

https://fishc.com.cn/forum.php?mod=collection&action=view&ctid=1661

哈，感谢