链表详解（python实现）

一、 定义见百度百科链表

链表由表头和节点组成，节点分为数据域和指针域，数据域中存贮数据元素，指针域存储下个结点的地址

二、单链表实现逻辑

创建节点类Node和链表类Linklist，Linklist类中包含head属性，head的值为0或Node对象，Node类中包含value属性存储数据，next属性存储下个节点的地址（Node对象）循环节点从head开始取next属性，直到next=0为止，返回当前对象添加节点时调用循环方法返回最后一个节点对象，把返回节点的next改为当前Node对象，如当前没有节点，则Linklist实例的head属性修改为当前Node对象删除节点时把前一个节点的next属性修改为后一个节点的Node对象，如果当前节点是最后一个对象

三、单链表代码实现

class Node: def __init__(self,value,node = 0): self.value = value self.next = node class LinkList: def __init__(self, value=0,*args): self.lenth = 0 #创建表头head self.head = 0 if value == 0 else Node(value) #如果初始化实例时传入多个参数，循环加入链表 p = self.head for i in [*args]: node = Node(i) p.next = node p = p.next def append(self,value): if self.head == 0: self.head = Node(value) else: self.iternodes().next = Node(value) def iternodes(self): p = self.head while p: print(p.value) if not p.next: return p p = p.next

四、双链表实现

对比单链表，Node对象增加了before属性记录前一节点对象，同时增加insert、pop等方法利用python的特殊方法，把Linklist类构造成一个类似list的类，可以使用len（）方法，可迭代 #创建Node类 class Node: def __init__(self, value, before=0, node=0): self.value = value self.next = node self.before = before #创建链表类 class LinkList: def __init__(self, value=0,*args): self.lenth = 0 #创建表头head self.head = 0 if value == 0 else Node(value) #如果初始化实例时传入多个参数，循环加入链表 if self.head != 0: self.lenth += 1 p = self.head for i in [*args]: node = Node(i) p.next = node node.before = p p = p.next self.lenth += 1 #append方法，判断表头是否为空，每次执行lenth属性值+1 def append(self, value): if self.head == 0: self.head = Node(value) self.lenth += 1 else: p = Node(value) cur = self.iternodes() cur.next = p p.before = cur self.lenth += 1 #insert方法（后插），是否表头特殊处理，每次执行lenth属性值+1 def instert(self, value, index): if self.head == 0: self.append(value) else: p = Node(value) prv = self.iternodes(index) if prv.__dict__.get('head'): p.before = prv.head prv.head.next = p if prv.head.next != 0: prv.head.next.before = p p.next = prv.head.next else: p.before = prv if prv.next != 0: prv.next.before = p p.next = prv.next prv.next = p self.lenth += 1 #遍历方法，每次从表头开始 def iternodes(self, index=None): if index is not None: if index > self.lenth: raise Exception("索引超界") p = self.head i = 0 while p: if i == index: return p p = p.next i += 1 else: p = self.head while p: if not p.next: return p p = p.next #删除方法，删除指定索引的值，表头特殊处理，每次执行lenth属性值-1 def pop(self, index=None): if self.lenth == 0: return 'LinkList is empty' if index is None: if self.lenth == 1: self.head = 0 self.lenth -= 1 return if self.iternodes().before == 0: self.iternodes().value = 0 else: self.iternodes().before.next = 0 elif index == 0: if self.iternodes(index).next == 0: self.head = 0 else: self.head.next.before = 0 self.head = self.head.next else: self.iternodes(index).before.next = self.iternodes(index).next self.iternodes(index).next.before = self.iternodes(index).before self.lenth -= 1 def __len__(self): return self.lenth def __iter__(self): yield from (self.iternodes(i) for i in range(self.lenth))