数据存储在结点Node中，该结点中有data用于存储数据，还有next用于指向下一个结点
优点：正在的动态数组，不需要处理固定容量的问题
缺点：丧失了随机访问的能力
有一个head指向链表的头部，访问链表的时候从链表头部开始向后遍历
在链表中添加元素1.在头部添加：
由于链表存在一个head，因此在链表头部添加元素最方便，只需要将新加入的结点的next指向头部，将新加入的结点设置为链表头部即可
2.在尾部添加结点：
从头开始找，直到找到某个节点的next为None（即最后一个结点），将最后一个结点的next指向新加入的结点即可
3.在中间加入结点：
找到插入位置的前一个结点，将新加入结点的next指向前一个结点的下一个结点node.next = pre.next
将前一个结点的next指向新加入的结点pre.next = node
注意：不能更改顺序，如果先将前一个结点的next指向新加入的node，那么将找不到下一个结点
class Node():
def __init__(self, ele):
self.data = ele
self.next = None
def __str__(self):
return str(self.data)
def __repr__(self):
return self.__str__()
class LinkList():
def __init__(self):
self.__head = None
self._size = 0
def get_size(self):
return self._size
def is_empty(self):
return self._size == 0
def add_first(self, ele):
node = Node(ele)
node.next = self.__head
self.__head = node
self._size += 1
def add_last(self, ele):
node = Node(ele)
if self.is_empty():
self.__head = node
self._size += 1
return
cur = self.__head
pre = None
while cur:
pre = cur
cur = cur.next
pre.next = node
self._size += 1
def add(self, index, ele):
if index < 0 or index > self._size:
raise Exception("索引错误！")
if index == 0:
self.add_first(ele)
return
node = Node(ele)
pre = self.__head
for i in range(index-1):
pre = pre.next
node.next = pre.next
pre.next = node
self._size +=1
def __str__(self):
curr = self.__head
data = []
while curr:
data.append(str(curr.data))
curr = curr.next
return "(Head)"+'->'.join(data)+' Tail'
def __repr__(self):
return self.__str__()
link = LinkList()
link.add_first(0)
link.add_last(100)
link.add(1,50)
link.add(1,20)
link.add(3,70)
print(link)
为链表设立虚拟头结点dummyhead
class LinkList_v2():
def __init__(self):
self.dummyhead = Node() # 添加一个虚拟头结点，注意修改Node中的ele默认为None
self._size = 0
def get_size(self):
return self._size
def is_empty(self):
return self._size == 0
def add_first(self, ele):
self.add(0, ele)
def add_last(self, ele):
self.add(self._size, ele)
def add(self, index, ele):
if index < 0 or index > self._size:
raise Exception('索引错误！')
pre = self.dummyhead
for i in range(index):
pre = pre.next
node = Node(ele)
node.next = pre.next
pre.next = node
self._size += 1
def __str__(self):
cur = self.dummyhead.next
data = []
while cur:
data.append(str(cur.data))
cur = cur.next
return '(Head) ' + '->'.join(data) + ' Tail'
def __repr__(self):
return self.__str__()
单向循环链表
将最后个结点指向头结点
class SingLinkList():
def __init__(self, node=None):
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():
return
cur = self.__head
while cur.next != self.__head:
print(cur.data, end=' ')
cur = cur.next
# 这种情况最后一个结点的data没有遍历到，因为最后一个结点的next就是头结点
# 因此要在后面进行输出
print(cur.data)
def add_first(self, ele):
node = Node(ele)
if self.is_empty():
self.__head = node
node.next = self.__head
else:
pre = self.__head
while pre.next != self.__head:
pre = pre.next
pre.next = node
node.next = self.__head
self.__head = node
def add_last(self, ele):
node = Node(ele)
if self.is_empty():
self.__head = node
node.next = self.__head
else:
pre = self.__head
while pre.next != self.__head:
pre = pre.next
pre.next = node
node.next = self.__head
def add(self, index, ele):
if index <= 0:
self.add_first(ele)
elif index > self.length() - 1:
self.add_last(ele)
else:
pre = self.__head
node = Node(ele)
for i in range(index - 1):
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, ele):
if self.is_empty():
return
cur = self.__head
pre = None
if cur.data == ele: # 如果删除的点刚好是头结点
if cur.next != self.__head: # 该循环链表不仅仅有一个结点
while cur.next != self.__head:
cur = cur.next
cur.next = self.__head.next
self.__head = self.__head.next
else:
self.__head = None
else:
pre = self.__head
while cur.next != self.__head:
if cur.data == ele:
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
if cur.data == ele:
pre.next = cur.next
def search(self, ele):
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.data == ele:
return True
cur = cur.next
if cur.data == ele:
return True
return False
def __str__(self):
cur = self.__head
data = []
# if cur.next == self.__head:
# data.append(str(cur.data))
# else:
while cur.next != self.__head:
data.append(str(cur.data))
cur = cur.next
data.append(str(cur.data))
return '(Head) ' + '->'.join(data) + ' Tail'
def __repr__(self):
return self.__str__()
双向链表
每个结点有三部分：
data：存储数据
pre：指向前一个结点
next：指向后一个结点
class BinNode():
def __init__(self, ele):
self.data = ele
self.pre = None
self.next = None
class BinaryLink():
def __init__(self, node=None):
self.__head = node
def is_elmpty(self):
return self.__head == None
def get_length(self):
if self.is_elmpty():
return 0
else:
cur = self.__head
count = 1
while cur.next != None:
count += 1
cur = cur.next
return count
def add_first(self, ele):
node = BinNode(ele)
if self.is_elmpty():
self.__head = node
node.next = None
node.pre = None
else:
node.next = self.__head
self.__head.pre = node
self.__head = node
def add(self, index, ele):
if index == 0:
self.add_first(ele)
elif index < 0 or index > self.get_length():
raise Exception("索引错误")
else:
cur = self.__head
for i in range(index-1):
cur = cur.next
node = BinNode(ele)
node.next = cur.next
node.pre = cur
if cur.next:
cur.next.pre = node
cur.next = node
# 第二种实现方式
# prev = None
# cur = self.__head
# for i in range(index):
# prev = cur
# cur = cur.next
#
# node = BinNode(ele)
# prev.next = node
# node.pre = prev
# node.next = cur
# if cur:
# cur.pre = node
def remove(self,ele):
if self.is_elmpty():
return
cur = self.__head
while cur:
if cur.data == ele:
if cur == self.__head:
if cur.next == None:
self.__head = None
else:
self.__head = self.__head.next
self.__head.pre = None
else:
cur.pre.next = cur.next
if cur.next:
cur.next.pre = cur.pre
break
else:
cur = cur.next
def search(self,ele):
cur = self.__head
while cur:
if cur.data == ele:
return True
else:
cur = cur.next
return False
def __str__(self):
cur = self.__head
data = []
# if cur.next == self.__head:
# data.append(str(cur.data))
# else:
while cur.next != None:
data.append(str(cur.data))
cur = cur.next
data.append(str(cur.data))
return '(Head) ' + '->'.join(data) + ' Tail'
def __repr__(self):
return self.__str__()
双向循环链表
head的pre指向最后一个结点
最后一个几点的next指向head
class BinNode():
def __init__(self, ele):
self.data = ele
self.pre = None
self.next = None
class DoubleLinklist():
def __init__(self, node=None):
self.__head = node
def is_empty(self):
return self.__head == None
def length(self):
if self.is_empty():
return 0
count = 1
cur = self.__head
while cur.next != self.__head:
count += 1
cur = cur.next
return count
def add_first(self, ele):
node = BinNode(ele)
if self.is_empty():
self.__head = node
node.next = node
node.pre = node
else:
node.next = self.__head
self.__head.pre.next = node
node.pre = self.__head.pre
self.__head.pre = node
self.__head = node
def add_last(self, ele):
node = BinNode(ele)
if self.is_empty():
self.__head = node
node.next = node
node.pre = node
else:
node.next = self.__head
self.__head.pre.next = node
node.pre = self.__head.pre
self.__head.pre = node
def add(self, index, ele):
if index <= 0:
self.add_first(ele)
elif index > self.length():
self.add_last(ele)
else:
node = BinNode(ele)
prev = self.__head
for i in range(index - 1):
prev = prev.next
node.next = prev.next
prev.next.pre = node
prev.next = node
node.pre = prev
def remove(self, ele):
if self.is_empty():
return
cur = self.__head
# 注意最后一个没有遍历
while cur.next != self.__head:
if cur.data == ele:
if cur == self.__head:
self.__head.pre.next = self.__head.next
self.__head.next.pre = self.__head.pre
self.__head = self.__head.next
else:
cur.pre.next = cur.next
cur.next.pre = cur.pre
cur.pre = None
cur.next = None
else:
cur = cur.next
if cur.data == ele:
cur.pre.next = cur.next
cur.next.pre = cur.pre
def __str__(self):
cur = self.__head
data = []
while cur.next != self.__head:
data.append(str(cur.data))
cur = cur.next
data.append(str(cur.data))
return "Heat--" + '->'.join(data) + ' Tail'
def __repr__(self):
return self.__str__()
静态链表
一个列表，第一个位置存储第一个空的位置索引，最后一个位置存第一个元素的索引
每个点有 cur和val两个属性，cur是下一个位置的索引，val是当前位置的值
优点：在顺序结构中，插入（删除）一个元素不需要移动所有的元素，只需更改cur即可
缺点：失去了顺序存储结构中随机访问的功能
class Node_v2():
def __init__(self, cur, val=None):
self.cur = cur
self.val = val
class Linklist():
def __init__(self, size=7):
self.maxz_size = size
self.node = list()
for i in range(self.maxz_size):
if i == self.maxz_size - 1:
self.node.append(Node_v2(0))
else:
self.node.append(Node_v2(i + 1))
def length(self):
leng = 0
i = self.node[self.maxz_size - 1].cur
while i:
leng += 1
i = self.node[i].cur
return leng
def findempty(self):
i = self.node[0].cur
if i:
self.node[0].cur = self.node[i].cur
return i
def add(self, index, ele):
if index < 1 or index > self.length() + 1 or self.length() == self.maxz_size - 2:
raise Exception("插入失败！")
j = self.findempty()
self.node[j].val = ele
k = self.maxz_size - 1
if j:
for i in range(1, index):
k = self.node[k].cur
self.node[j].cur = self.node[k].cur
self.node[k].cur = j
def remove(self, index):
if index < 1 or index > self.length():
raise Exception("删除失败")
k = self.maxz_size - 1
for i in range(index - 1):
k = self.node[k].cur
del_index = self.node[k].cur
self.node[k].cur = self.node[del_index].cur
self.delempty(del_index)
def delempty(self, index):
self.node[index].cur = self.node[0].cur
self.node[0].cur = index
def __str__(self):
i = self.node[self.maxz_size - 1].cur
data = []
while i:
data.append(str(self.node[i].val))
i = self.node[i].cur
return '-->'.join(data)
def __repr__(self):
return self.__str__()
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）