浅谈Python数据结构(五)--链表

最近学习了python数据结构，做一些必要的笔记，一来是对自己学习的知识的巩固，二来对有同样问题的人有参考作用

---

---

一 单向链表

1、定义

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

代码实现：

class Node:
    def __init__(self,item):
        self.item = item # 数据
        self.next = None # 下一个节点的指针

2、创建链表

（1）头插法

代码实现：

def create_linklist_head(li):
    head = Node(li[0])
    for element in li[1:]:
        node = Node(element)
        node.next = head
        head = node
    return head

（2）尾插法

代码实现：

def create_linklist_tail(li):
    head = Node(li[0])
    tail = head
    for element in li[1:]:
        node = Node(element)
        tail.next = node
        tail = node
    return head

3、遍历链表

代码实现

def print_linklist(lk):
    while lk:
        print(lk.item,end=",")
        lk = lk.next
    print()

4、插入和删除操作

（1）插入

代码实现：

p.next = curNode.next
curNode.next = p

（2）删除

代码实现：

curNode.next = p.next
del p

二 双向链表

1、定义

双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点。

代码实现：

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

2、创建链表

代码实现：

def create_linklist_te(li):
    head = Node(li[0])
    tail = head
    for element in li[1:]:
        node = Node(element)
        tail.next = node
        node.prior = tail
        tail = node
    return (head,tail)

3、遍历链表

代码实现：

def print_linklist_tw(lk,choice=1):
    if choice > 0: # 表示正向遍历
        while lk:
            print(lk.item,end=",")
            lk = lk.next
    else: # 表示反向遍历
        while lk:
            print(lk.item,end=",")
            lk = lk.prior
    print()

4、双向链表的插入和删除

（1）插入

代码实现：

p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p

（2）删除

代码实现：

curNode.next = p.next
p.next.prior = curNode
del p

5、双向链表实现队列

优点：既能实现队列的功能，也能不会造成空间浪费。

代码实现：

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

class Queue:
    def __init__(self):
        self.head = None
        self.tail = self.head

    def append(self,data):
        node = Node(data)
        if self.tail:
            self.tail.next = node
            node.prior = self.tail
            self.tail = node
        else:
            self.head = node
            self.tail = self.head

    def popleft(self):
        if self.head:
            data = self.head.item
            self.head.next.prior = None
            self.head = self.head.next
            return data
        else:
            print("队空异常")

q = Queue()
q.append(5)
q.append(2)
print(q.popleft())

三 顺序表和链表对比

对比项 \ 名称	顺序表	链表
按值查找	O(n)	O(n)
按下标查找	O(1)	O(n)
在某元素后插入	O(n)	O(1)
在某元素后删除	O(n)	O(1)

链表在存储数据的时候空间可以不连续。

---

四 总结

如有错误恳请指正，如有雷同纯属巧合