数据结构笔记：单向链表
原文地址
分类目录——数据结构笔记
离散存储，手拉手，每一块有指向下一块的指针（形象描述，python中没有指针），就好像形成了一条链
一个元素包括两部分：value 和 next
链表与顺序表都是线性表
知识点补充
b = 20
a = 'achar'
a = b
# 在python中，所有的变量保存的都是值的地址（就相当于c语言中的指针）
# 等号右边表示执行，=b中的b就是执行，根据值的地址取到b的值，就成了a=20，而这时的操作，是把20的地址返给a；也因此，在python中，之前给a的字符串变量可以在之后换成int的变量，这次其他语言中是不能实现的。
# 等号实质上是改变了数据指向
在链表实现时，为next赋值即是这种机制
节点类
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
链表类及常用方法实现
构造的时候要考虑到特殊情况，常用参考项有链表为空时，链表只有一个元素时，链表尾部时。
class SinglCycleLinkList(object):
def __init__(self, node=None):
self.head = None
if node: # 每加入一个节点，就是一个指向自己的循环链表？
node.next = node
def is_empty(self):
'''判断链表是否为空'''
return self.head == 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():
return
cur = self.head # 指针
while cur.next != self.head:
print(cur.value, end=' ')
cur = cur.next
print(cur.value)
def add(self, value):
'''头部插入——头插法'''
node = Node(value)
if self.is_empty():
self.head = node
node.next = self.head
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
node.next = self.head # 把新节点夹在head之前
self.head = node # 链表的新头部编程node
cur.next = self.head # 尾部指向新头部
def append(self, value):
'''尾部插入——尾插法'''
node = Node(value)
if self.is_empty():
self.head = node
node.next = self.head
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
node.next = self.head
def insert(self, index, value):
'''
:param index: the position of insert(start from 0)
:param value: node.value
:return:
'''
node = Node(value)
if index self.length():
self.append(value)
else:
cur = self.head
count = 0
while count < index - 1:
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
'''从链表中删除item'''
# 如果为空
if self.head == None:
return
# 如果第一个命中
if self.head.value == item:
# 如果只有一个元素
if self.length() == 1:
self.head = None
return
else:
rear = self.head # 用这个索引去找尾
while rear.next != self.head:
rear = rear.next
self.head = self.head.next
rear.next = self.head
else:
cur = self.head
while cur.next != self.head and cur.next.value != item:
cur = cur.next
if cur.next.value == item:
cur.next = cur.next.next
def search(self, item):
'''在链表中查找item，含有返回True，不含返回False（因为是链表，返回索引也没有意义）'''
if self.is_empty():
return False
cur = self.head
if cur.value == item:
return True
else:
while cur != self.head:
cur = cur.next
if cur.value == item:
return True
return False
测试
if __name__ == '__main__':
sll1 = SinglLinkList()
print(sll1.is_empty())
print(sll1.length())
sll1.append(6)
print(sll1.is_empty())
sll1.add(10)
sll1.append(7)
sll1.append(8)
print(sll1.length())
sll1.insert(4, 22)
sll1.travel()
sll1.remove(10)
sll1.travel()
sll1.remove(7)
sll1.travel()
sll1.remove(22)
sll1.travel()
sll1.remove(10)
sll1.travel()
顺序表与链表
链表可以实现分类内存 链表无法直接定位到表中元素，增删改查都需要遍历表，时间复杂度相对更高一些；顺序表可以直接定位元素 在中间插入上，顺序表的时间复杂度也是O(n)，其时间消耗在于保序操作上；链表中的时间操作在于定位上作者：BBJG_001
