共计 6377 个字符，预计需要花费 16 分钟才能阅读完成。
怎么创立链表？想要弄懂链表的创立，那么咱们首要的指标应该是搞懂什么叫做链表。那么说道链表，不得不提的就是数组了，那么什么是数组呢？python 中是没有数组这个概念的，python 中用列表和元组代替了这一概念。那么数组的特点是什么？
在内存地址中，它的表现形式是用一片间断的空间来存储数据，这个就是数组的概念，那么链表呢？
概念
链表是一种物理存储单元上非间断、非程序的存储构造，然而它还是属于一种线性表，因为在每一个节点外面都会寄存下一个节点的信息 next。
单链表
每个节点蕴含两个局部，一部分存放数据变量的 data，另一部分寄存下一个节点的地位信息 next。
class Node():
"""节点类"""
def __init__(self, item, next=None):
self.item = item
self.next = next
class LinkList():
"""链表"""
def __init__(self, node=None):
self.head = node
def is_empty(self):
"""判断链表是否为空"""
return True if self.head else False
def length(self):
"""返回链表长度"""
num = 0
node = self.head
if node == None:
return num
num += 1
while node.next:
node = node.next
num += 1
return num
def add(self, item):
"""链表头部增加"""
self.head = Node(item, self.head)
def travel(self):
"""遍历整个链表"""
node = self.head
if node == None:
return
print(node.item)
while node.next:
node = node.next
print(node.item)
def addend(self, item):
"""链表尾部增加元素"""
node = self.head
if node == None:
self.head = Node(item)
return
while node.next:
node = node.next
node.next = Node(item)
def insert(self, index, item):
"""指定地位增加"""
if index == 0:
self.add(item)
return
node = self.head
try:
for i in range(index):
node = node.next
node.next = None(item, node.next)
except:
assert "索引超出范围"
def remove(self, index):
"""删除指定节点"""
if index == 0:
self.head = self.head.next
return
node = self.head
try:
for i in range(index-1):
node = node.next
node.next = node.next.next
except:
assert "索引超出范围"
def search(self, item):
"""查找节点是否存在"""
index = 0
node = self.head
while node.next:
if node.item==item:
return index
index += 1
node = node.next
return "该元素不存在"双向链表
除了蕴含单链表的局部，还存储了一个前一个节点的地位信息 prev。
class Node():
"""节点类"""
def __init__(self, item, per=None, next=None):
self.per = per
self.item = item
self.next = next
class LinkList():
"""双向链表"""
def __init__(self, node=None):
self.head = node
def is_empty(self):
"""判断链表是否为空"""
return True if self.head else False
def length(self):
"""返回链表长度"""
num = 0
node = self.head
if node == None:
return num
num += 1
while node.next:
node = node.next
num += 1
return num
def add(self, item):
"""链表头部增加"""
self.head = Node(item, next=self.head)
def travel(self):
"""遍历整个链表"""
node = self.head
if node == None:
return
print(node.item)
while node.next:
node = node.next
print(node.item)
def addend(self, item):
"""链表尾部增加元素"""
node = self.head
if node == None:
self.head = Node(item)
return
while node.next:
node = node.next
node.next = Node(item, node)
def insert(self, index, item):
"""指定地位增加"""
if index == 0:
self.add(item)
return
node = self.head
try:
for i in range(index):
node = node.next
node.next = None(item, node, node.next)
except:
assert "索引超出范围"
def remove(self, index):
"""删除指定节点"""
if index == 0:
self.head = self.head.next
return
node = self.head
try:
for i in range(index-1):
node = node.next
node.next = node.next.next
except:
assert "索引超出范围"
def search(self, item):
"""查找节点是否存在"""
index = 0
node = self.head
while node.next:
if node.item==item:
return index
index += 1
node = node.next
return "该元素不存在"循环链表
链表构造与之前一样，只是链表的最初一个 next 指向了链表头，造成了一个循环。
class Node():
"""节点类"""
def __init__(self, item, per=None, next=None):
self.per = per
self.item = item
self.next = next
class LinkList():
"""循环链表"""
def __init__(self, node=None):
self.head = node
def is_empty(self):
"""判断链表是否为空"""
return True if self.head else False
def length(self):
"""返回链表长度"""
num = 0
node = self.head
if node == None:
return num
num += 1
while node.next!=self.head:
node = node.next
num += 1
return num
def add(self, item):
"""链表头部增加"""
self.head = Node(item, per=self.head.per, next=self.head)
def travel(self):
"""遍历整个链表"""
node = self.head
if node == None:
return
print(node.item)
while node.next!=self.head:
node = node.next
print(node.item)
def addend(self, item):
"""链表尾部增加元素"""
node = self.head
if node == None:
node = Node(item)
node.per=node
node.next=node
self.head = node
return
while node.next:
node = node.next
node.next = Node(item, node, node.next)
def insert(self, index, item):
"""指定地位增加"""
if index == 0:
self.add(item)
return
node = self.head
try:
for i in range(index):
node = node.next
node.next = None(item, node, node.next)
except:
assert "索引超出范围"
def remove(self, index):
"""删除指定节点"""
if index == 0:
self.head = self.head.next
return
node = self.head
try:
for i in range(index-1):
node = node.next
node.next = node.next.next
node.next.per=node
except:
assert "索引超出范围"
def search(self, item):
"""查找节点是否存在"""
index = 0
node = self.head
while node.next:
if node.item==item:
return index
index += 1
node = node.next
return "该元素不存在"链表，就是这么解释、创立的。
正文完
