【数据结构】双向链表、单向循环链表、双向循环链表、栈、链栈

目录

一、双向链表

定义类和封装函数以及测试样例如下：

注意事项：

二、循环链表

单循环列表的类和函数封装如下：

注意事项： 

三、双向循环链表

结点类和双循环链表的定义部分

函数封装之判空和尾插

双循环链表遍历

双循环链表尾删

完整测试以及结果：

四、栈

顺序栈

顺序栈本质以及组成

顺序栈的操作

链栈

---

一、双向链表

对于单向链表而言。只能通过头节点或者第一个节点出发，单向的访问后继节点，每个节点只能记录其后继节点的信息（位置），不能向前遍历。

所以引入双向链表，双向链表可以保持单向链表特点的基础上，让每个节点，既能向后访问后继节点，也可以向前访问前驱节点。

相较于单向链表，我们更多的是在每个结点上加入了一个前驱链接域

定义类和封装函数以及测试样例如下：

class Node(object):def __init__(self,data):self.next = Noneself.prior = Noneself.data = dataclass DoubleLinklist(object):def __init__(self):self.head = Noneself.size = 0def is_empty(self):return self.size == 0def add_head(self,value):node=Node(value)if self.is_empty():self.head = nodeself.size+=1else:node.next = self.headself.head.prior = nodeself.head = nodeself.size += 1def show_me(self):if self.is_empty():print('空表查看不了')else:q = self.headwhile q :print(q.data,end=' ')q = q.nextdef add_anywhere(self,location,value):if location < 1 or location > self.size+1:print('插入失败')else:node = Node(value)if location == 1:self.add_head(value)else:q = self.headi = 1while i< location-1:q = q.nexti += 1if q.next is None:q.next = nodenode.prior = qelse:node.next = q.nextnode.prior = qq.next.prior = nodeq.next = nodeself.size+=1def del_anywhere(self,location):if self.is_empty() or location < 1 or location > self.size:print('删除失败')else:if location == 1:self.head = self.head.nextself.head.prior = Noneelse:q=self.headi =1while i < location :q = q.nexti += 1if  q.next :q.prior.next = q.nextq.next.prior = q.priorelse:q.prior.next = Noneself.size -=1def find_node(self,value):if self.is_empty():print('查找失败')else:q = self.headwhile q:if q.data == value:return Trueq = q.nextreturn Falseif __name__ == '__main__':new_l=DoubleLinklist()print('头插')new_l.add_head(50)new_l.add_head(40)new_l.add_head(30)new_l.add_head(20)new_l.add_head(10)new_l.show_me()print()print('任意位置插入')new_l.add_anywhere(1,666)new_l.add_anywhere(7,666)new_l.add_anywhere(3,666)new_l.show_me()print()print('任意位置删除')new_l.del_anywhere(8)new_l.del_anywhere(3)new_l.del_anywhere(1)new_l.show_me()print()print('找是否存在值30')print(new_l.find_node(30))print()

结果如下：

注意事项：

对链表的删除和插入操作我们均要考虑空表、末尾元素、单个元素情况；双循环链表的插入操作 :                       node.next = q.next
                    node.prior = q
                    q.next.prior = node
                    q.next = node

这四条语句除了第一条的位置不能变动以外（防止丢失结点），后面的操作前后顺序没有强制要求。

---

二、循环链表

循环链表：就是首尾相连的链表，通过任意一个节点，都能将整个链表遍历一遍

单循环列表的类和函数封装如下：

class Node(object):def __init__(self,data):self.data = dataself.next = Noneclass CirculateLinkList(object):def __init__(self):self.head = Noneself.size = 0def is_empty(self):return self.size == 0def add_tail(self,value):node = Node(value)if self.is_empty():self.head = nodenode.next = nodeelse:q = self.headi = 1while i < self.size:q = q.nexti += 1q.next = nodenode.next = self.headself.size += 1def show_me(self):if self.is_empty():print('空表')elif self.size == 1 :print(self.head.data)else:q = self.headi = 1while i < self.size+1:  #q要定位到第一个结点才能遍历完print(q.data,end=' ')q=q.nexti += 1def del_tail(self):if self.is_empty():print('删除失败')elif self.size == 1 :self.head = Noneself.size -=1else:q = self.headi = 1while i < self.size-1 :q = q.nexti+=1q.next = self.headself.size -= 1if __name__ == '__main__':new_l=CirculateLinkList()print('尾插')new_l.add_tail(30)new_l.add_tail(20)new_l.add_tail(10)new_l.show_me()print()print('尾删')new_l.del_tail()new_l.del_tail()new_l.show_me()print()

结果：

注意事项： 

基本注意事项不再赘述，这里有个格外要注意的点：

    def show_me(self):
        if self.is_empty():
            print('空表')
        elif self.size == 1 :
            print(self.head.data)
        else:
            q = self.head
            i = 1
            while i < self.size+1:  #q要定位到第一个结点才能遍历完
                print(q.data,end=' ')
                q=q.next
                i += 1

while循环要多循环一次，使得q指向第一个结点才能遍历完整

---

三、双向循环链表

双循环链表同样需要考虑几个点，如何创建，如何增删改查，由于是双向的，那么可以不用像单向的删除操作中一定要找到删除元素前一个位置，可以直接定位到要删除的位置，只需要把前驱后继都重新分配好即可。

结点类和双循环链表的定义部分

class Node(object):def __init__(self,data):self.data=dataself.next=Noneself.prior=Noneclass DoubleCirculateLinkList(object):def __init__(self):self.head=Noneself.size=0

函数封装之判空和尾插

 注意：尾插部分要注意分空表和单元素情况

    def is_empty(self):return self.size == 0def add_tail(self,value):node=Node(value)if self.is_empty():self.head=nodenode.next=nodenode.prior=nodeelif self.size == 1:self.head.next=nodeself.head.prior=nodenode.next=self.headnode.prior=self.headelse:q=self.headwhile True:q=q.nextif q.next==self.head:breaknode.next=self.headnode.prior=qq.next=nodeself.head.prior=nodeself.size+=1

这里的常规尾插我用到的遍历循环是while True：内部增加一个判断退出的条件来获得末尾结点q

情况全分析完毕整体判断外size+=1即可

双循环链表遍历

遍历涉及到打印，我们用一个变量q来记录，常规情况下要遍历到最后一个结点，但这还不够，要执行的下去循环内的打印语句才行，所以要留意。

 def show_me(self):if self.is_empty():print('空表')else:q=self.headwhile True:print(q.data,end=' ')q=q.nextif q ==self.head:break

双循环链表尾删

首先，空表无法删除，单元素删除直接head==None，常规情况可直接遍历到最后一个结点（由于是双向的链表所以不用找倒数第二个结点了），然后将该结点的前驱结点next指向head，head指向的结点的前驱再指向回来即可删除。

    def del_tail(self):if self.is_empty():print('空表')elif self.size == 1:self.head = Noneelse:q=self.headwhile True:q=q.nextif q.next==self.head:breakq.prior.next=self.headself.head.prior=q.priorself.size-=1

完整测试以及结果：

class Node(object):def __init__(self,data):self.data=dataself.next=Noneself.prior=Noneclass DoubleCirculateLinkList(object):def __init__(self):self.head=Noneself.size=0def is_empty(self):return self.size == 0def add_tail(self,value):node=Node(value)if self.is_empty():self.head=nodenode.next=nodenode.prior=nodeelif self.size == 1:self.head.next=nodeself.head.prior=nodenode.next=self.headnode.prior=self.headelse:q=self.headwhile True:q=q.nextif q.next==self.head:breaknode.next=self.headnode.prior=qq.next=nodeself.head.prior=nodeself.size+=1def show_me(self):if self.is_empty():print('空表')else:q=self.headwhile True:print(q.data,end=' ')q=q.nextif q ==self.head:breakdef del_tail(self):if self.is_empty():print('空表')elif self.size == 1:self.head = Noneelse:q=self.headwhile True:q=q.nextif q.next==self.head:breakq.prior.next=self.headself.head.prior=q.priorself.size-=1if __name__ == '__main__':new_l=DoubleCirculateLinkList()print('尾插')new_l.add_tail(10)new_l.add_tail(20)new_l.add_tail(30)new_l.add_tail(40)new_l.add_tail(50)new_l.show_me()print()print('尾删')new_l.del_tail()new_l.del_tail()new_l.show_me()print()

---

四、栈

顺序栈

顺序存储的栈即是顺序栈

顺序栈本质以及组成

本质上：顺序栈是一个只允许在栈顶进行插入和删除操作的顺序表，遵循LIFO

需要使用一个容器存储一个栈，例如列表

顺序栈的操作

这里直接使用内置函数去对栈封装

class Stack(object):def __init__(self):self.data = []def is_empty(self):return self.data == []def push(self,value):self.data.insert(0,value)def pop(self):self.data.pop(0)def show(self):for i in self.data:print(i,end=' ')print()def get_top_value(self):return self.data[0]def get_size(self):return len(self.data)

链栈

既然顺序栈就是对栈顶元素增删的特殊的顺序表，那么链栈就是对栈顶元素增删的特殊的单向链表

这里我的pop不仅实现了删除，而且还增加了额外的返回值

代码如下：

class Node(object):def __init__(self,data):self.data=dataself.next=Noneclass LinkStack(object):def __init__(self):self.size=0self.head=Nonedef is_empty(self):return self.size==0def push(self,value):node=Node(value)node.next=self.headself.head=nodeself.size+=1def pop(self):if self.is_empty():print('空栈')else:q=self.head.dataself.head=self.head.nextself.size-=1return qdef show(self):if self.is_empty():print('空栈')else:q=self.headwhile q:print(q.data,end=' ')q=q.nextdef get_top_value(self):if self.is_empty():return Noneelse:return self.head.datadef get_size(self):return self.size

---

未完待续（持续跟新中）🏆