Num01-->链表的定义
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。
这里写图片描述
Num02-->链表中单向链表
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
这里写图片描述
1、表元素域elem用来存放具体的数据。
2、链接域next用来存放下一个节点的位置（python中的标识）
3、变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
案例采用Python代码实现如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author : xiaoke
class Node(object):
"""结点类"""
def __init__(self, item):
"""
初始化函数
:param item: 要保存的用户数据
"""
self.item = item
self.next = None
class SingleLinkList(object):
"""单链表"""
def __init__(self, node=None):
"""
初始化函数
:param node: 可传可不传的头结点
"""
# 指向头结点
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head is None
def length(self):
"""链表长度"""
cur = self.__head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur is not None:
print(cur.item, end=" ")
cur = cur.next
print("") # 多输出换行
def add(self, item):
"""链表头部添加元素"""
node = Node(item)
node.next = self.__head
self.__head = node
def append(self, item):
"""链表尾部添加元素"""
node = Node(item)
# 如果是空链表
if self.is_empty():
self.__head = node
else:
# 寻找尾结点
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
"""指定位置添加元素"""
# 在头结点插入元素
if pos <= 0:
self.add(item)
# 在链表的尾部添加元素
elif pos >= self.length():
self.append(item)
# 在链表的任意位置添加元素
else:
cur = self.__head
count = 0
# 找到添加位置的前一个位置
while count < (pos - 1):
count += 1
cur = cur.next
node = Node(item)
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除节点
:param: item 要删除的元素
"""
cur = self.__head
pre = None
while cur is not None:
# 找到了元素
if cur.item == item:
# 在头部找到了元素
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
return
pre = cur
cur = cur.next
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur is not None:
# 找到了元素返回真
if cur.item == item:
return True
cur = cur.next
return False
# 开始测试
if __name__ == '__main__':
ll = SingleLinkList()
print(ll.length())
ll.append(1)
print(ll.length())
ll.travel()
ll.append(2)
print(ll.length())
ll.travel()
ll.add(3)
ll.travel()
ll.add(4)
ll.travel()
ll.insert(0, 5)
ll.travel()
ll.insert(10, 6)
ll.travel()
ll.insert(3, 7)
ll.travel()
ll.remove(5)
ll.travel()
ll.remove(6)
ll.travel()
ll.remove(7)
ll.travel()
ll.remove(4)
ll.travel()
ll.remove(3)
ll.travel()
ll.remove(1)
ll.travel()
ll.remove(2)
ll.travel()
# 结果如下：
# 0
# 1
# 1
# 2
# 1 2
# 3 1 2
# 4 3 1 2
# 5 4 3 1 2
# 5 4 3 1 2 6
# 5 4 3 7 1 2 6
# 4 3 7 1 2 6
# 4 3 7 1 2
# 4 3 1 2
# 3 1 2
# 1 2
# 2
#
Num03-->链表中双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
这里写图片描述
案例采用Python代码实现如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author : xiaoke
class Node(object):
"""结点"""
def __init__(self, item):
self.item = item
self.next = None
self.pre = None
class DoubleLinkList(object):
"""双向链表"""
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head is None
def length(self):
"""链表长度"""
cur = self.__head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
cur = self.__head
while cur is not None:
print(cur.item, end=" ")
cur = cur.next
print("") # 多输出换行
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur is not None:
# 找到了元素返回真
if cur.item == item:
return True
cur = cur.next
return False
def add(self, item):
"""链表头部添加元素"""
node = Node(item)
# 如果是空链表
if self.is_empty():
self.__head = node
else:
node.next = self.__head
self.__head.pre = node
self.__head = node
def append(self, item):
"""链表尾部添加元素"""
node = Node(item)
# 如果是空链表
if self.is_empty():
self.__head = node
else:
# 寻找尾结点
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
node.pre = cur
def insert(self, pos, item):
"""指定位置添加元素"""
# 在头结点插入元素
if pos <= 0:
self.add(item)
# 在链表的尾部添加元素
elif pos >= self.length():
self.append(item)
# 在链表的任意位置添加元素
else:
cur = self.__head
count = 0
# 找到添加位置
while count < pos:
count += 1
cur = cur.next
node = Node(item)
node.next = cur
node.pre = cur.pre
cur.pre = node
node.pre.next = node
def remove(self, item):
"""删除节点
:param: item 要删除的元素
"""
cur = self.__head
while cur is not None:
# 找到了元素
if cur.item == item:
# 在头部找到了元素
if cur == self.__head:
self.__head = cur.next
if cur.next:
cur.next.pre = None
else:
cur.pre.next = cur.next
if cur.next:
cur.next.pre = cur.pre
return
cur = cur.next
if __name__ == '__main__':
ll = DoubleLinkList()
print(ll.length())
ll.append(1)
print(ll.length())
ll.travel()
ll.append(2)
print(ll.length())
ll.travel()
ll.add(3)
ll.travel()
ll.add(4)
ll.travel()
ll.insert(0, 5)
ll.travel()
ll.insert(10, 6)
ll.travel()
ll.insert(3, 7)
ll.travel()
ll.remove(5)
ll.travel()
ll.remove(6)
ll.travel()
ll.remove(7)
ll.travel()
ll.remove(4)
ll.travel()
ll.remove(3)
ll.travel()
ll.remove(1)
ll.travel()
ll.remove(2)
ll.travel()
# 结果如下：
# 0
# 1
# 1
# 2
# 1 2
# 3 1 2
# 4 3 1 2
# 5 4 3 1 2
# 5 4 3 1 2 6
# 5 4 3 7 1 2 6
# 4 3 7 1 2 6
# 4 3 7 1 2
# 4 3 1 2
# 3 1 2
# 1 2
# 2
#
Num04-->链表中单向循环链表
单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。
这里写图片描述
案例采用Python代码实现如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author : xiaoke
class Node(object):
"""结点类"""
def __init__(self, item):
"""
初始化函数
:param item: 要保存的用户数据
"""
self.item = item
self.next = None
class CycleSingleLinkList(object):
"""循环单链表"""
def __init__(self, node=None):
"""
初始化函数
:param node: 可传可不传的头结点
"""
# 指向头结点
self.__head = node
def is_empty(self):
"""链表是否为空"""
return self.__head is None
def length(self):
"""链表长度"""
if self.is_empty():
return 0
cur = self.__head
count = 1
while cur.next != self.__head:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历整个链表"""
if self.is_empty():
print("")
return
cur = self.__head
while cur.next != self.__head:
print(cur.item, end=" ")
cur = cur.next
# 退出循环时指向尾结点
print(cur.item, end=" ")
print("") # 多输出换行
def add(self, item):
"""链表头部添加元素"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
# 寻找尾结点
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
self.__head = node
cur.next = node
def append(self, item):
"""链表尾部添加元素"""
node = Node(item)
# 如果是空链表
if self.is_empty():
self.__head = node
node.next = node
else:
# 寻找尾结点
cur = self.__head
while cur.next != self.__head:
cur = cur.next
cur.next = node
node.next = self.__head
def insert(self, pos, item):
"""指定位置添加元素"""
# 在头结点插入元素
if pos <= 0:
self.add(item)
# 在链表的尾部添加元素
elif pos >= self.length():
self.append(item)
# 在链表的任意位置添加元素
else:
cur = self.__head
count = 0
# 找到添加位置的前一个位置
while count < (pos - 1):
count += 1
cur = cur.next
node = Node(item)
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除节点
:param: item 要删除的元素
"""
if self.is_empty():
return
cur = self.__head
pre = None
while cur.next != self.__head:
# 找到了元素
if cur.item == item:
# 在头部找到了元素
if cur == self.__head:
rear = self.__head
while rear.next != self.__head:
rear = rear.next
# rear到达了尾结点
self.__head = cur.next
rear.next = self.__head
else:
pre.next = cur.next
pre = cur
cur = cur.next
# 退出循环后，cur指向尾结点
if cur.item == item:
if pre:
# pre.next = cur.next
pre.next = self.__head
else:
# 链表只有一个结点
self.__head = None
def search(self, item):
"""查找节点是否存在"""
cur = self.__head
while cur.next != self.__head:
# 找到了元素返回真
if cur.item == item:
return True
cur = cur.next
# 退出循环后，cur指向尾结点
if cur.item == item:
return True
return False
if __name__ == '__main__':
ll = CycleSingleLinkList()
print(ll.length())
ll.append(1)
print(ll.length())
ll.travel()
ll.append(2)
print(ll.length())
ll.travel()
ll.add(3)
ll.travel()
ll.add(4)
ll.travel()
ll.insert(0, 5)
ll.travel()
ll.insert(10, 6)
ll.travel()
ll.insert(3, 7)
ll.travel()
ll.remove(5)
ll.travel()
ll.remove(6)
ll.travel()
ll.remove(7)
ll.travel()
ll.remove(4)
ll.travel()
ll.remove(3)
ll.travel()
ll.remove(1)
ll.travel()
ll.remove(2)
ll.travel()
# 结果如下：
# 0
# 1
# 1
# 2
# 1 2
# 3 1 2
# 4 3 1 2
# 5 4 3 1 2
# 5 4 3 1 2 6
# 5 4 3 7 1 2 6
# 4 3 7 1 2 6
# 4 3 7 1 2
# 4 3 1 2
# 3 1 2
# 1 2
# 2
#
Num05-->链表与顺序表的对比
链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。
链表与顺序表的各种操作复杂度如下所示：
这里写图片描述
注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。
链表的主要耗时操作是遍历查找，删除和插入,操作本身的复杂度是O(1)。
顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。
