怎么创立链表？想要弄懂链表的创立，那么咱们首要的指标应该是搞懂什么叫做链表。那么说道链表，不得不提的就是数组了，那么什么是数组呢？python中是没有数组这个概念的，python中用列表和元组代替了这一概念。那么数组的特点是什么？
在内存地址中，它的表现形式是用一片间断的空间来存储数据，这个就是数组的概念，那么链表呢？
概念
链表是一种物理存储单元上非间断、非程序的存储构造，然而它还是属于一种线性表，因为在每一个节点外面都会寄存下一个节点的信息next。
单链表
每个节点蕴含两个局部，一部分存放数据变量的data，另一部分寄存下一个节点的地位信息next。
class Node(): """节点类""" def __init__(self, item, next=None): self.item = item self.next = nextclass 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 = nextclass 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 = nextclass 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 "该元素不存在"链表，就是这么解释、创立的。