Python数据结构实战——双向链表(DoublyLinkedList)
1.定义结点类
class Node: def __init__(self, data=None,next=None,prev=None): self.data = data self.next = next self.prev = prev
2.定义链表类
class DoublyLinkedList: def __init__(self): self.head = None
2.1.打印正向链表
def print_forward(self): if self.head is None: print("Linked list is empty") return itr = self.head #指针指向头部 llstr = while itr: llstr += str(itr.data) + "-->" #拼接指针 itr = itr.next print(llstr)
2.2.打印反向链表
def print_backward(self): if self.head is None: print("Linked list is empty") return last_node = self.get_last_node() itr = last_node #获取最后一个结点 llstr = while itr: llstr += itr.data + --> itr = itr.prev #指针由前往后移 print("Link list in reverse:",llstr)
2.3.寻找链表最后一个结点
def get_last_node(self): itr = self.head while itr.next: itr = itr.next return itr #找到最后一个结点
2.4.计算链表长度
def get_length(self): count = 0 itr = self.head while itr: count += 1 itr = itr.next #指针后移 return count
2.5.链表首部插入元素
def insert_at_begining(self,data): node = Node(data,self.head,None) #新建一个结点,新的结点的指针指向当前头结点 self.head.prev = node #当间结点的前向指针指向新的结点 self.head = node #新的头结点为node
2.6.链表尾部插入元素
def insert_at_end(self,data): if self.head is None: self.head = Node(data, None, None) #如果是空链表,新建一个没有前后指针的结点 return itr = self.head while itr.next: #只要当前结点还有指针,一直往后移,直到当前结点没有指针 itr = itr.next itr.next = Node(data,None,itr) #把新的结点插入尾部,新插入的结点前向指针指向itr
2.7.链表任意位置插入元素
def insert_at(self, index, data): if index<0 or index>self.get_length(): #判断是否越界 raise Exception("Invalid Index") if index == 0: #如果在头结点插入 self.insert_at_begining(data) return count = 0 itr = self.head while itr: if count == index-1: node = Node(data, itr.next, itr) #新建一个结点,有前后指针 if node.next: #如果当前结点有下一个结点 node.next.prev = node #当前结点的下一个结点的前向指针指向当前结点 itr.next = node #插入结点 break itr = itr.next count += 1
2.8.链表任意位置删除元素
def remove_at(self, index, data): if index<0 or index>=self.get_length(): raise Exception("Invalid Index") if index==0: self.head = self.head.next self.head.prev = None return count = 0 itr = self.head while itr: if count == index: #找到被删除位置 itr.prev.next = itr.next #itr的前一个结点的后向指针指向itr的下一个结点 if itr.next: #如果存在下一个结点 itr.next.prev = itr.prev #下一个结点的前向指针指向itr的前一个结点 break itr = itr.next count += 1
2.9.链表中插入一堆元素
def insert_values(self,data_list): self.head = None for data in data_list: self.insert_at_end(data)
3.测试
ll = DoublyLinkedList() ll.insert_values(["banana","mango","grapes","orange"]) #链表中插入一堆元素 ll.print_forward() #打印正向链表 ll.print_backward() #打印反向链表 ll.insert_at_end("figs") #链表尾部插入元素 ll.print_forward() ll.print_backward() ll.insert_at(0,"jackfruit") #任意位置插入元素 ll.print_forward() ll.insert_at(6,"dates") ll.print_forward() ll.insert_at(2,"kiwi") ll.print_forward()
上一篇:
IDEA上Java项目控制台中文乱码