一、链表

1.  单向链表

 链表（linked list）是一种在物理上非连续、非顺序的数据机构，由若干节点（node）所组成。

单向 链表的每一个节点又包含两部分，一部分是存放数据的变量data， 另一部分是指向下一个节点的指针next。

# 单向链表初始化
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的next指针指向空。

2. 双向链表

双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

3. 链表的基本操作

a. 查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

例如给出一个链表，从头节点开始，查找第3个节点：

第1步，将查找的指针定位到头节点；

第2步，根据头节点的next指针，定位到第2个节点；

第3步，根据第2个节点的next指针，定位到第3个节点。

b. 更新节点

如果不考虑查找的过程，链表更新节点直接把旧数据替换成新数据即可。

c. 插入节点

与数组类似，同样分为3种情况：

• 尾部插入
• 头部插入
• 中间插入

尾部插入直接把最后一个节点的next指针指向新插入的节点即可：

头部插入，可以分成两个步骤：
第1步，把新节点的next指针指向原先的头节点。
第2步，把新节点变为链表的头节点。

中间插入，同样分为两个步骤：
第1步，新节点的next指针指向插入位置的节点。
第2步，插入位置前置节点的next指针，指向新节点。

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

d. 删除元素

链表的删除操作同样分为3种情况：

• 尾部删除
• 头部删除
• 中间删除

尾部删除直接把倒数第2个节点的next指针指向空即可：

头部删除把链表的头节点设为原先头节点的next指针所指向的节点即可：

中间删除把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可：

实现链表的完整代码：

 1 class Node:
 2     def __init__(self, data):
 3         self.data = data
 4         self.next = None
 5     
 6 
 7 class LinkedList:
 8     def __init__(self):
 9         self.size = 0
10         self.head = None
11         self.last = None
12     
13     def get(self, index):
14         if index < 0 or index >= self.size:
15             raise Exception('超出链表节点范围')
16         p = self.head
17         for i in range(index):
18             p = p.next
19         return p
20         
21     def insert(self, data, index):
22         if index < 0 or index >= self.size:
23             raise Exception('超出链表节点范围')
24         node = Node(data)
25         if self.size == 0:
26             # 空链表
27             self.head = node
28             self.last = node
29         elif index == 0:
30             # 插入头部
31             node.next = self.head
32             self.head = node
33         elif self.size == index:
34             # 插入尾部
35             self.last.next = node
36             self.last = node
37         else:
38             # 插入中间
39             prev_node = self.get(index-1)
40             removed_node = prev_node.next
41             prev_node.next = node
42         self.size += 1
43         
44     def remove(self, index):
45         if index < 0 or index >= self.size:
46             raise Exception('超出链表节点范围')
47         # 暂存被删除的节点，用于返回
48         if index == 0:
49             # 删除头节点
50             removed_node = self.head
51             self.head = self.head.next
52         elif index == self.size - 1:
53             # 删除尾节点
54             prev_node = self.get(index-1)
55             removed_node = prev_node.next
56             prev_node.next = None
57             self.last = prev_node
58         else:
59             # 删除中间节点
60             prev_node = self.get(index-1)
61             next_node = prev_node.next.next
62             removed_node = prev_node.next
63             prev_node.next = next_node
64             self.size -= 1
65             return removed_node
66     
67     def output(self):
68         p = self.head
69         while p is not None:
70             print(p.data)
71             p = p.next
72 
73 
74 linkedList = LinkedList()
75 linkedList.insert(3, 0)
76 linkedList.insert(4, 0)
77 linkedList.insert(9, 2)
78 linkedList.insert(5, 3)
79 linkedList.insert(6, 1)
80 linkedList.remove(0)
81 linkedList.output()

 4. 数组和链表

数组和链表相关操作的对比：

数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些。相反地，链表的优势在于能够灵活地进行插入和删除操作，如果需要频繁插入、删除元素，用链表更合适一些。