python——链表、双链表、链栈、链队列

链表类的定义：

创建链表——头插法

创建链表——尾插法

二、双链表

定义双链表

双链表——插入p节点

双链表——删除

小结

三、链栈

四、链队列

自学视频：B站-路飞学城-清华大学博士讲解python数据结构与算法

一、链表

介绍：链表是由一系列节点组成的元素集合，每个节点包含两个部分，数据域item 和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表

链表类的定义：

class Node(object):
    def __init__(self, item):
        self.item = item   # 存数据
        self.next = None   # 存当前节点的下一个节点

测试：

if __name__ == '__main__':
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n1.next = n2
    n2.next = n3

    print(n1.next.item)   # 2
    print(n1.next.next.item)   # 3
    print(n1.next.next.next.item)   # 报错

创建链表——头插法

新来的节点成为新的头结点head，倒序排列

def create_linklist(li):
    head = Node(li[0])
    for element in li[1:]:
        node = Node(element)   # 创建一个节点
        node.next = head
        head = node
    return head

测试：

lk = create_linklist([1, 2, 3])
print_linklist(lk)

创建链表——尾插法

新来的节点成为尾结点tail，顺序排列

def create_link_tail(li):
    head = Node(li[0])
    tail = head
    for element in li[1:]:
        node = Node(element)  # 创建一个节点
        tail.next = node
        tail = node
    return head

测试：

lk1 = create_link_tail([1,2,3])
print_linklist(lk1)

二、双链表

定义双链表

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prior = None

双链表——插入p节点

p.next = curNode.next

curNode.prior = p

p.prior = curNode

curNode.next = p

双链表——删除

定义p指向要删除的节点

p = curNode.next

curNode.next = p.next

p.next.prior = curNode

小结

链表与顺序表

链表在插入删除的操作上明显快于顺序表
链表的内存可更灵活的分配
利用链表实现栈和队列
链表的链式存储结构对树和图的结构有很大的启发性

三、链栈

# 定义链节点类
class LinkNode(object):
    def __init__(self, data):
        self.data = data   # 存数据
        self.next = None   # 存当前节点的下一个节点


# 链栈
class LinkStack(object):
    def __init__(self):
        self.top = LinkNode(None)  # 定义栈顶为空

    # 进栈
    def push(self, e):
        node = LinkNode(e)   # 创建一个新节点
        node.next = self.top   # 新节点的下一个指向top
        self.top = node    # top指向新节点

    # 出栈
    def pop(self):
        if self.top is None:
            print("栈为空！")
            exit()
        out_data = self.top.data
        self.top = self.top.next
        return out_data

    # 判空
    def is_empty(self):
        return self.top is None

    # 取栈顶元素
    def get_top(self):
        if self.top is None:
            print("栈为空！")
            return None
        return self.top.data

测试：

if __name__ == '__main__':
    ls = LinkStack()
    for element in range(5):
        ls.push(element)
    print(ls.get_top())
    print(ls.pop())
    print(ls.is_empty())

结果：

四、链队列

# 定义一个链表类
class LinkNode(object):
    def __init__(self, data):
        self.data = data
        self.next = None


# 定义一个链队列
class QueueLink(object):
    def __init__(self):
        temp_node = LinkNode(None)   # 创建一个空的链表节点
        self.rear = temp_node  # 队尾指针，指向空节点
        self.front = temp_node  # 队首指针，指向空节点

    # 创建一个链队列
    def create_linkQueue(self, li):
        for element in li:
            self.EnQueue(element)

    # 判空
    def is_empty(self):
        if self.front == self.rear:
            return True
        else:
            return False

    # 求队长
    def LenghQueue(self):
        head = self.front
        count = 0
        while head.next:
            count += 1
            head = head.next
        return count

    # 入队
    def EnQueue(self, e):
        node = LinkNode(e)   # 创建一个新节点
        if self.is_empty():
            self.front.next = node
        self.rear.next = node
        self.rear = node

    # 出队
    def DeQueue(self):
        if self.is_empty():
            print("队列为空！")
            exit()
        else:
            temp = self.front.next   # 定义temp指向队首元素
            self.front.next = temp.next   # 让front的next指针指向队首元素的下一个
            if self.rear == temp:
                # 该节点为尾结点
                self.front = self.rear
            return temp.data

    def Traverse(self):
        head = self.front
        while head.next:
            head = head.next
            print(head.data, end=" ")
        print(" ")

    def GetQueue(self):
        return self.front.next.data

测试：

if __name__ == '__main__':
    q1 = QueueLink()
    q1.create_linkQueue([1, 2, 3, 4, 5, 6])
    print("队列元素如下")
    q1.Traverse()
    print("队列的长度为{}".format(q1.LenghQueue()))
    print("队首元素为{}".format(q1.GetQueue()))
    for element in range(q1.LenghQueue()):
        print(q1.DeQueue(), end=" ")

结果：