链表

数组（Python中的列表）的结构实现如下：

对于101 25 36如果采用数组的形式存储的话如下图所示：

数组在使用中需要事先预估要存储的数据的个数，一次性申请存储空间。查找元素时速度很快，但是在在扩充时会非常慢。需要重新申请一块新的内存地址。

链表可以解决顺序表扩充时的不足，链表扩充时，原存储不变，加一个扩一个，事先无需进行预估。

链表的节点结构如下：

，data为数据区，next为地址，指向下一个节点。

链表的节点结构如下图，其中head用于保存首位节点的地址，地址是无需连续得：

接下来用Python实现链表，并实现相关属性：

上代码：

  1 # 节点类
  2 class LinklistNode:
  3     """节点"""
  4     def __init__(self, x):
  5         """
  6         elem：节点保存的数据
  7         next：保存指向下一个节点的地址
  8         """
  9         self.value = x
 10         self.next = None  # 由于此时不知道下一个节点的地址，此处初始化为空
 11 
 12 
 13 # 链表类，最终会由节点类来构造成链表，包括链表的各种属性
 14 class SinglelinkList:
 15     """单向链表"""
 16 
 17     def __init__(self, node=None):  # 这里对于node参数，如果传入数值则赋值，否则就使用默认值None
 18         self.__head = node  # 通过head找到头节点。对于节点的头部地址只对类内使用，不对外暴露，所以使用私有属性
 19 
 20     def is_empty(self):
 21         """链表是否为空"""
 22         return self.__head == None
 23 
 24     def length(self):
 25         """链表长度"""
 26         cur = self.__head  # cur用来移动遍历节点
 27         count = 0  # 记录数量，赋值为0与下面的判断条件结合很好的处理了空列表的情况
 28         while cur != None:  # 为什么不用cur.next != None，这个需要举例确定，与计数的初始值有关
 29             count += 1
 30             cur = cur.next  # 移动到下一个节点
 31         return count
 32 
 33     def travel(self):
 34         """遍历整个列表"""
 35         cur = self.__head
 36         while cur != None:
 37             print(cur.element, end=" ")
 38             cur = cur.next
 39 
 40     def addlast(self, data):  # 传入的是一个数，而不是一个节点，这样用户在使用中无需关心什么节点
 41         """链表尾部添加元素"""
 42         node = LinklistNode(data)
 43         if self.__head == None:
 44             self.__head = node
 45         else:
 46             cur = self.__head
 47         while cur.next != None:
 48             cur = cur.next
 49         cur.next = node
 50 
 51     def addhead(self, data):
 52         """链表头部添加元素，头插法"""
 53         node = LinklistNode(data)
 54         node.next = self.__head
 55         self.__head = node
 56 
 57     def insert(self, pos, data):
 58         """指定位置添加元素"""
 59         """
 60         :pos，由自己定义，从0开始，将data添加到pos位置，链表不同于顺序表，链表要找到某一位置，必须遍历
 61         """
 62         node = LinklistNode(data)
 63         if pos <= 0:
 64             # 此处认为使用头插法
 65             self.addhead(data)
 66         elif pos > (self.length() - 1):  # 此处不含等于号
 67             # 此处认为使用尾插法
 68             self.addlast(data)
 69         else:
 70             cur = self.__head
 71             count = 0
 72             while count <= (pos - 1):
 73                 cur = cur.next
 74                 count += 1
 75             # 等循环退出之后，cur指向pos-1的位置上，进行操作
 76             node.next = cur.next
 77             cur.next = node
 78 
 79     def search(self, data):
 80         """查找指定元素是否存在，遍历+比对"""
 81         cur = self.__head
 82         while cur != None:
 83             if cur.elem == data:
 84                 return True
 85             else:
 86                 cur = cur.next
 87         return False  # 考虑，对于空列表此处也可以实现
 88 
 89     def remove(self, data):
 90         """删除节点"""
 91         cur = self.__head
 92         pre = None  # 程序中，常使用 pre 或者 prior 来表示前一个
 93         while cur != None:
 94             if cur.value == data:
 95                 # 判断此节点是否为头节点
 96                 if cur == self.__head:
 97                     self.__head = cur.next
 98                 else:
 99                     pre = cur
100                     pre.next = cur.next
101                     break
102             else:
103                 cur = cur.next
104         """
105         在删除列表这个操作中要重点考虑以下四种特殊情况：
106         1.空列表
107         2.删除首节点
108         3.删除首节点且只有一个节点
109         4.删除尾结点
110         """
111 
112 
113 # 到此基本实现了链表的所有属性，下面对代码进行测试
114 if __name__ == "__main__":
115     ll = SinglelinkList()
116     print(ll.is_empty())
117     print(ll.length())
118     ll.remove(2)
119 
120     ll.addhead(1)
121     print(ll.is_empty())
122     print(ll.length())
123     ll.remove(1)
124 
125     ll.addhead(2)
126     ll.addhead(3)
127     ll.addhead(4)
128     ll.addhead(5)
129     ll.addhead(6)
130     ll.addhead(7)
131     print(ll.is_empty())
132     print(ll.length())
133 
134     ll.insert(-1, 9)
135     ll.insert(3, 100)
136     ll.remove(100)
137     print(ll.is_empty())
138     print(ll.length())

链表是数据结构之一，其中的数据呈线性排列。在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。

关键点：
实际上，相比较数组来说，并不存在链表这样一个对象，链表是由多个节点组成的，因此，我们能接触到的数据对象只有节点。我们可以根据节点来寻找周围节点，许多节点之间的关系抽象地构成了一个链表。