本文不涉及链表概念的详细讲解，而着重利用 python 实现链表，在其中穿插代码讲解。本文主要实现单向链表、单向循环链表、双向链表。

其它数据结构：栈和队列、二叉树。

链表有多个节点，第一个节点称为头节点，最后一个节点称为尾节点。中间节点的前一个节点称为前驱节点，后一个节点称为后继节点。每个链表都有一个 head 指针，指向这个链表的头节点。链表可以获取其长度，也可以增加或删除节点，遍历节点。

节点

链表有若干个节点串联而成。对于单向链表而言，每个节点有两个区域，分别存放数据和后继节点。

class Node():
    """节点，保存数据和后继节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

• 1
• 2
• 3
• 4
• 5

在双向链表中，每个节点不仅指向后继节点，还可以指向前驱节点，因此节点中还有有个区域存放前驱节点。

class Node():
    """双向链表节点"""
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.pre = None

• 1
• 2
• 3
• 4
• 5
• 6

单向链表

单向链表只能从第一个节点开始向后搜索，直到最后一个结点。

构造链表

每个链表均有一个 head 值指向头节点；如果是空链表，则指向 None。

class Linklist():
    def __init__(self, node=None):
        self.__head = node

• 1
• 2
• 3

是否为空

如果 head 值指向 None，则说明是个空链表。

def is_empty(self):
    """判断链表是否为空"""
    return self.__head == None

• 1
• 2
• 3

遍历链表

指针 cur 从指向头节点开始，沿着每个节点的 next 值指向后继节点，直至尾节点 next 指向 None。

def travel(self):
    """遍历链表"""
    cur = self.__head

    while cur != None:
        print(cur.elem)
        cur = cur.next

• 1
• 2
• 3
• 4
• 5
• 6
• 7

获取长度

要知道链表的长度就要遍历一遍链表，并记录下节点个数。

def length(self):
    """返回链表长度"""
    cur = self.__head
    
    count = 0
    while cur != None:
        count += 1
        cur = cur.next
    return count

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

插入元素

尾部插入

在尾部插入新的节点，只需要把最后一个节点的 next 区域改为新插入的节点，新插入节点的 next 区域指向 None。

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

这里只需要传入值，在函数内构造节点。

头部插入

要在链表头部添加元素，则需要让 head 指向这个新节点，让新节点的 next 指向原有的头节点。

def add(self, item):
    """在链表头部添加"""
    node = Node(item)

    node.next = self.__head
    self.__head = node

• 1
• 2
• 3
• 4
• 5
• 6

中间插入

指定新节点插入位置，让前驱节点的 next 指向新节点，让新节点的 next 指向原有节点的后继节点。

def insert(self, pos, item):
    """在指定位置插入节点"""
    # 如果 pos < 0，则认为在头部插入
    if pos <= 0:
        self.add(item)
        # 如果 pos > length，则认为在尾部插入
    elif pos > self.length() - 1:
        self.append(item)
    else:
        pre = self.__head
        # 找到指定位置
        count = 0
        while count < pos - 1:
            count += 1
            pre = pre.next

        # 插入节点
        node = Node(item)
        node.next = pre.next
        pre.next = node

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20

查找节点

输入一个数据，判断这个数据是否在链表之中，同样需要遍历链表。

def search(self, item):
    """查找节点是否存在"""
    cur = self.__head

    while cur != None:
        if cur.elem == item:
            return True
        else:
            cur = cur.next

    return False

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

删除节点

给定一个值，从链表中删除第一个出现这个值的节点。找到即将删除节点的前驱节点，让其的 next 设置为要删除节点的后继节点。

def remove(self, item):
    """删除节点"""
    cur = self.__head

    # 如果删除的节点是头节点
    if cur.elem == item:
        self.__head = cur.next
    else:
    	# 找到删除节点的前驱节点
        while cur.next.elem != item:
            cur = cur.next
		cur.next = cur.next.next

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

使用单向链表

在 main 方法中对上述方法进行测试。

if __name__ == '__main__':
    ll = Linklist()
    print(ll.is_empty())
    print(ll.length())

    ll.append(100)
    print(ll.is_empty())
    print(ll.length())

    ll.append(200)
    ll.append(300)
    print(ll.length())
    ll.travel()

    ll.add(-100)
    ll.travel()

    ll.insert(-1, -666)
    ll.insert(2, 123)
    ll.insert(10, 12345)
    ll.travel()

    print(ll.search(888))
    print(ll.search(123))
    
    ll.remove(-666)
    ll.travel()
    ll.remove(12345)
    ll.travel()
    ll.remove(123)
    ll.travel()

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31

单向循环链表

单向循环链表与单链表十分相似，只不过单向循环链表的尾节点可以指向头节点，而不是指向 None。

构造链表

在单向循环链表构造时，如果传入了一个节点，则该节点的 next 指向自己。

class Cycle_Linklist():
    def __init__(self, node=None):
        """单向循环链表构造"""
        self.__head = node
        if node:
            node.next = node

• 1
• 2
• 3
• 4
• 5
• 6

是否为空

判断链表是否为空与单向链表相同，不再赘述。

遍历链表

单向循环链表中尾节点的 next 不再指向 None，而是指向头节点，遍历停止条件为指向头节点，单独考虑链表为空的情况。

def travel(self):
    """遍历链表"""
    cur = self.__head

    if self.is_empty():
        print()
    else:
        while cur.next != self.__head:
            print(cur.elem, end=' ')
            cur = cur.next
        print(cur.elem)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

注意不要漏掉尾节点。

链表长度

计算链表长度同样需要遍历链表。

def length(self):
    """返回链表长度"""
    cur = self.__head

    if self.is_empty():
        return 0

    count = 1
    while cur.next != self.__head:
        count += 1
        cur = cur.next

    return count

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

插入元素

尾部插入

让原有的尾节点指向新节点，并让新节点的 next 指向头节点。

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
        
        # 指向新节点
        cur.next = node
        node.next = self.__head

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

头部插入

从头部插入新节点，需要将 __head 指向新插入节点，同时把尾节点的 next 插入新节点，并把新节点的 next 指向原来的头节点。

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.next = node
        node.next = self.__head
        self.__head = node

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

中间插入

在中间插入的情况与单向链表相同，不再赘述。

查找节点

查找节点同样需要遍历链表。

def search(self, item):
    """查找节点是否存在"""
    cur = self.__head

    if self.is_empty():
        return False

    while cur.next != self.__head:
        if cur.elem == item:
            return True
        else:
            cur = cur.next
    if cur.elem == item:
        return True

    return False

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

删除节点

如果删除的节点不是头节点，则与单向链表相同；如果是头节点，则还需要把尾节点的 next 指向第二个节点。

def remove(self, item):
    """删除节点"""
    cur = self.__head

    # 如果删除的节点是头节点
    if cur.elem == item:
        # 遍历找到最后一个节点
        tail = cur
        while tail.next != self.__head:
            tail = tail.next
        tail.next = cur.next
        self.__head = cur.next
    else:
        # 找到删除节点的前驱节点
        while cur.next.elem != item:
            cur = cur.next
        cur.next = cur.next.next

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

使用单向循环链表

单向循环链表的测试与单向链表相同，不再赘述。

双向链表

在双向链表中，每个节点不仅指向后继节点，还可以指向前驱节点。

构造链表

双向循环链表的初始化与单向链表相同，不再赘述。

是否为空

双向循环链表判断为空与单向链表相同，不再赘述。

遍历链表

双向链表的遍历可以按照单向链表遍历思路，不再赘述。

获取长度

获取双向链表的长度也可以按照单向链表遍历思路，不再赘述。

插入元素

尾部插入

在尾部插入新节点，需要把新节点的 pre 指向原来链表的尾节点。

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.pre = cur

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

头部插入

在头部插入新节点时，让新节点的 next 区域指向原来链表的头节点，原来链表的头节点指向新节点，head 也指向新节点。

def add(self, item):
    """在链表头部添加"""
    node = Node(item)

    self.__head.pre = node
    node.next = self.__head
    self.__head = node

• 1
• 2
• 3
• 4
• 5
• 6
• 7

中间插入

除了进行单向链表的插入过程之外，还需要修改节点的 pre。

def insert(self, pos, item):
    """在指定位置插入节点"""
    # 如果 pos < 0，则认为在头部插入
    if pos <= 0:
        self.add(item)
        # 如果 pos > length，则认为在尾部插入
    elif pos > self.length() - 1:
        self.append(item)
    else:
        cur = self.__head
        # 找到指定位置
        count = 0
        while count < pos - 1:
            count += 1
            cur = cur.next

        # 插入节点
        node = Node(item)
        node.next = cur.next
        node.pre = cur
        cur.next = node
        node.next.pre = node

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

查找节点

双向链表查找元素与单向链表相同，不再赘述。

删除节点

不仅要修改删除节点的前驱节点的 next，单独考虑删除的节点是尾节点的情况，还要修改删除节点的后继节点的 pre。

def remove(self, item):
    """删除节点"""
    cur = self.__head

    # 如果删除的节点是头节点
    if cur.elem == item:
        self.__head = cur.next
        cur.next.pre = None
    else:
        # 找到删除节点的前驱节点
        while cur.next.elem != item:
            cur = cur.next
        
        # 如果要删除的节点不是尾节点
        if cur.next.next != None:
            cur.next.next.pre = cur
        cur.next = cur.next.next

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

使用双向链表

使用方法与单向链表相同，不再赘述。