1. 双向链表的定义
每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
2. 操作
- is_empty() 链表是否为空
- length() 链表长度
- travel() 遍历链表
- add(item) 链表头部添加
- append(item) 链表尾部添加
- insert(pos, item) 指定位置添加
- remove(item) 删除节点
- search(item) 查找节点是否存在
3. 实现
class Node(object): def __init__(self,item): self.elem = item self.next = None self.prev = None class DoubleLinkList(object): ''' 双链表 ''' def __init__(self,node=None): self.__head = node def is_empty(self): #判断链表是否为空 return self.__head is None def length(self): #链表的长度 #cur游标，用来遍历节点，count记录数量 cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): #遍历链表 cur = self.__head while cur != None: print(cur.elem,end=' ') cur = cur.next print('') def add(self,item): #在链表头部添加节点 node = Node(item) node.next = self.__head self.__head = node node.next.prev = node def append(self,item): #在链表尾部添加节点 node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur
在链表指定位置插入元素
def insert(self,pos,item): #在链表指定位置添加节点 # pos从0开始 if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: cur = self.__head count = 0 while count < pos: count += 1 cur = cur.next #当退出循环后,pre指向pos位置 node = Node(item) # node.next = cur # node.prev = cur.prev # cur.prev.next = node # cur.prev = node node.prev = cur #将node的prev指向cur node.next = cur.next #将node的next指向cur的下一个节点 cur.next.prev = node #将cur的下一个节点的prev指向node cur.next = node #将cur的next指向node
移除和查找节点
def remove(self,item): #移除节点 cur = self.__head while cur != None: if cur.elem == item: #先判断此节点是否是头节点 #头节点 if cur == self.__head: self.__head = cur.next if cur.next: #判断链表是否只有一个节点 cur.next.prev = None else: cur.prev.next = cur.next if cur.next: cur.next.prev = cur.prev break else: cur = cur.next def search(self,item): #查找节点 cur = self.__head while cur != None: if cur.elem == item: return True else: cur = cur.next return False
完整代码：
class Node(object): def __init__(self,item): self.elem = item self.next = None self.prev = None class DoubleLinkList(object): ''' 双链表 ''' def __init__(self,node=None): self.__head = node def is_empty(self): #判断链表是否为空 return self.__head is None def length(self): #链表的长度 #cur游标，用来遍历节点，count记录数量 cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): #遍历链表 cur = self.__head while cur != None: print(cur.elem,end=' ') cur = cur.next print('') def add(self,item): #在链表头部添加节点 node = Node(item) node.next = self.__head self.__head = node node.next.prev = node def append(self,item): #在链表尾部添加节点 node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur def insert(self,pos,item): #在链表指定位置添加节点 # pos从0开始 if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: cur = self.__head count = 0 while count < pos: count += 1 cur = cur.next #当退出循环后,pre指向pos位置 node = Node(item) # node.next = cur # node.prev = cur.prev # cur.prev.next = node # cur.prev = node node.prev = cur #将node的prev指向cur node.next = cur.next #将node的next指向cur的下一个节点 cur.next.prev = node #将cur的下一个节点的prev指向node cur.next = node #将cur的next指向node def remove(self,item): #移除节点 cur = self.__head while cur != None: if cur.elem == item: #先判断此节点是否是头节点 #头节点 if cur == self.__head: self.__head = cur.next if cur.next: #判断链表是否只有一个节点 cur.next.prev = None else: cur.prev.next = cur.next if cur.next: cur.next.prev = cur.prev break else: cur = cur.next def search(self,item): #查找节点 cur = self.__head while cur != None: if cur.elem == item: return True else: cur = cur.next return False if __name__ == '__main__': dll = DoubleLinkList() print(dll.is_empty()) print(dll.length()) dll.append(1) print(dll.is_empty()) print(dll.length()) dll.append(2) dll.add(8) dll.append(3) dll.append(4) dll.append(5) dll.append(6) dll.insert(-1,9) dll.travel() dll.insert(3,100) dll.travel() dll.insert(10,200) dll.travel() dll.remove(100) dll.travel() dll.remove(9) dll.travel() dll.remove(200) dll.travel() ''' 运行结果 True 0 False 1 9 8 1 2 3 4 5 6 9 8 1 2 100 3 4 5 6 9 8 1 2 100 3 4 5 6 200 9 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 '''
单向循环链表
1. 单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。
2. 操作
- is_empty() 判断链表是否为空
- length() 返回链表的长度
- travel() 遍历
- add(item) 在头部添加一个节点
- append(item) 在尾部添加一个节点
- insert(pos, item) 在指定位置pos添加节点
- remove(item) 删除一个节点
- search(item) 查找节点是否存在
3. 实现
class Node(object): #单向循环链表节点类实现 def __init__(self,elem): self.elem = elem self.next = None class SingleCycleLinkList(object): #单向循环链表类实现 def __init__(self,node=None): self.__head = node if node: node.next = node def is_empty(self): #判断链表是否为空 return self.__head == None def length(self): #链表的长度 if self.is_empty(): return 0 #cur游标，用来遍历节点，count记录数量 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.elem,end=' ') cur = cur.next #退出循环，cur指向尾节点，但尾节点的元素未打印 print(cur.elem) def add(self,item): #在链表头部添加节点 node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next #退出循环，cur指向尾节点 node.next = self.__head self.__head = node cur.next = node def append(self,item): #在链表尾部添加节点 node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next node.next = self.__head cur.next = node def insert(self,pos,item): #在链表指定位置添加节点 # pos从0开始 if pos <= 0: self.add(item) elif pos > (self.length()-1): self.append(item) else: pre = self.__head count = 0 while count < (pos-1): count += 1 pre = pre.next #当退出循环后,pre指向pos-1位置 node = Node(item) node.next = pre.next pre.next = node def remove(self,item): #移除节点 if self.is_empty(): return cur = self.__head pre = None while cur.next != self.__head: if cur.elem == item: #先判断此节点是否是头节点 if cur == self.__head: #头节点的情况 #先找到尾节点 rear = self.__head while rear.next != self.__head: rear = rear.next self.__head = cur.next rear.next = self.__head else: #中间节点 pre.next = cur.next return else: pre = cur cur = cur.next #退出循环,cur指向尾节点 if cur.elem == item: if cur == self.__head: #链表只有一个节点 self.__head = None else: pre.next = cur.next def search(self,item): #查找节点 if self.is_empty(): return False cur = self.__head while cur.next != self.__head: if cur.elem == item: return True else: cur = cur.next #退出循环，cur指向尾节点 if cur.elem == item: return True return False if __name__ == '__main__': ll = SingleCycleLinkList() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(2) ll.add(8) ll.append(3) ll.append(4) ll.append(5) ll.append(6) ll.insert(-1,9) ll.travel() ll.insert(3,100) ll.travel() ll.insert(10,200) ll.travel() ll.remove(100) ll.travel() ll.remove(9) ll.travel() ll.remove(200) ll.travel() ''' 运行结果： True 0 False 1 9 8 1 2 3 4 5 6 9 8 1 100 2 3 4 5 6 9 8 1 100 2 3 4 5 6 200 9 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 200 8 1 2 3 4 5 6 '''