03-13 7,580 views
数据结构是大学必修的一门课程。每一位开发人员从开始工作就在接触数据结构，一直贯穿整个职业生涯，除非你转向其它行业。所以数据结构是很重要的一门课程。
数据结构包括线性数据结构、树等。其中线性结构包括: 链表、堆栈、队列、双端队列、环状队列等。树包括：二叉树、二叉堆、二叉查找树、平衡二叉树等。其实数据结构的知识还是很多的，今天咱们就说一下线性结构中的链表数据结构。
谈到链表之前，先说一下线性表。线性表是最基本、最简单也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是收尾相接的。线性表友两种存储方式，一种是顺序存储结构，另外一种是链表存储结构。
顺序存储结构就是两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为O(1),通过首地址和偏移量就可以直接访问到该元素，关于查找的适配算法很多，最快可以达到O(logn)。缺点是插入和删除的时间复杂度最坏能达到O(n),如果你在第一个位置插入一个元素，你需要把数组的每一个元素向后移动一位，如果你在第一个位置删除一个元素，你需要把数组的每一个元素向前移动一位。还有一个缺点，就是当你不确定元素的数量时，你开的数组必须保证能够放下元素最大数量，遗憾的是如果实际数量比最大数量少很多时，你开的数组没有用到的内存就只能浪费掉了。
我们常用的数组就是一种典型的顺序存储结构.
链表存储结构就是两个相邻的元素在内存中可能不是相邻的，每一个元素都有一个指针域,指针域一般是存储着到下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1),不会浪费太多内存，添加元素的时候才会申请内存，删除元素会释放内存。缺点是访问的时候时间复杂度最坏为O(n)，关于查找的算法很少，一般只能遍历，这样时间复杂度也是线性(O(n))的了,频繁的申请和释放内存也会消耗时间。
顺序表的特性是随机读取，也就是访问一个元素的时间复杂度是O(1)，链式表的特性是插入和删除的时间复杂度为O(1)。要根据实际情况去选取适合自己的存储方式.
链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表和循环链表等。
咱们今天用python来实现一个单向链表，每个元素博阿含两个域。值域和指针域，我们把这样的元素称之为节点。每个节点的指针域内有一个指针，指向下一个节点，而最后一个节点则指向一个空值。
一个单向链表的节点被分成两个部分。第一部分保存或者显示关于节点的信息，第二部分存储下一个节点的地址。单向链表只可向一个方向遍历。
下面用python来实现一个单向链表。
＃LinkList.py
class Node:
'''该类实例化一个元素节点.'''
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
'''实现一个单向链表.'''
def __init__(self):
'''初始化链表.
初始化时,为一个空链表.链表有两个标示head和tail都赋值None.
'''
self.head = None
self.tail = None
def append(self, data):
'''向链表新增元素.
1. 如果该链表是一个空链表,则链表head和tail都指向传进来的node节点.
2. 如果链表非空,则self.tail.next = node.next 指向新插入元素.
tail指向新插入的元素节点.
'''
node = Node(data)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def insert(self, idx, value):
'''向链表插入一个元素node.
1. 从链表头开始遍历链表,当查找的index小于要插入索引的位置时，依次
指向下一个元素节点.直到找到要插入节点的索引位置.
2. 首先将插入的值,通过Node类实例化一个元素node.然后将它的next指针
指向它的下一个元素.即当前新元素节点之前的元素索引位置.
3. 将当前元素索引指向新插入元素node.
'''
cur = self.head
cur_idx = 0
while cur_idx < idx - 1:
cur = cur.next
if cur.next is None:
raise Exception('list length less than index')
cur_idx += 1
node = Node(value)
node.next = cur.next
cur.next = node
if cur.next is None:
self.tail = node
def inter(self):
'''返回一个链表迭代器.
1. 首先判断该链表是否为一个空链表。如果时一个空链表,直接返回.
2. 如果是一个非空链表,首先指针指向head节点,然后将head节点data
返回.然后while循环,条件是下一个指针元素为真.然后弹出下一个元
素data,直到遍历到最后一个元素.
'''
if not self.head:
return
cur = self.head
yield cur.data
while cur.next:
cur = cur.next
yield cur.data
def remove(self, idx):
'''从链表中删除一个元素节点.
1. 首先找到要删除的元素节点索引.
2. 然后将当前节点的next指向下一个下一个元素节点.
'''
cur = self.head
cur_idx = 0
while cur_idx < idx-1:
cur = cur.next
if cur is None:
raise Exception('list length less than index')
cur_idx +=1
cur.next = cur.next.next
if cur.next is None:
self.tail = cur
if __name__ == "__main__":
linked_list = LinkedList()
# 循环插入元素
for i in range(10):
linked_list.append(i)
# 向元素插入一个元素
linked_list.insert(3, 40)
# 向元素删除一个元素
linked_list.remove(4)
# 遍历该链表
for node in linked_list.inter():
print(node)
