博客

详解Python将元素添加到链表的第一个和最后一个位置

  • Post category:Python

下面是Python程序将元素添加到链表的第一个和最后一个位置的详细讲解及完整使用攻略。

一、添加元素到链表第一个位置

1.1 实现原理

链表是由节点构成的链式结构，每个节点都包含两部分内容：数据和指针。在链表的头部插入元素，就是把插入的元素作为新的节点，然后将原来头部节点的指针指向新的节点，新的节点的指针指向原来的头部节点。具体实现过程如下图所示：

    +------+      +-----+      +-----+      +-----+
    | head |  ->  | data|  ->  | data|  ->  | data|
    +------+      | ptr |      | ptr |      | ptr |
                   +-----+      +-----+      +-----+

插入新元素后：

    +------+      +-----+      +-----+      +-----+
    | data |      | head|  ->  | data|  ->  | data|
    | ptr  |  ->  +-----+      | ptr |      | ptr |
    +------+                 +-----+      +-----+

1.2 代码实现

可以通过 Node 类来实现节点的创建，添加数据和指向下一个节点的指针。然后定义 LinkedList 类来实现链表的基本操作，如添加元素到链表头部，遍历链表等操作。

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

class LinkedList:
    def __init__(self):
        self.head = None

    def add_to_start(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def traverse(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

# Test the code
ll = LinkedList()
ll.add_to_start(1)
ll.add_to_start(2)
ll.add_to_start(3)
ll.traverse()

输出结果为：

3
2
1

1.3 示例说明

示例一

def test1():
    ll = LinkedList()
    ll.add_to_start('c')
    ll.add_to_start('b')
    ll.add_to_start('a')
    ll.traverse()

输出结果为：

a
b
c

示例二

def test2():
    ll = LinkedList()
    ll.add_to_start(3)
    ll.add_to_start(2)
    ll.add_to_start(1)
    ll.traverse()

输出结果为：

1
2
3

二、添加元素到链表最后

2.1 实现原理

链表的尾部添加元素，就是通过遍历链表找到尾节点，然后将新的节点连接到尾节点后面，更新指针即可。具体实现过程如下所示：

    +------+      +-----+      +-----+      +-----+
    | head |  ->  | data|  ->  | data|  ->  | tail|
    +------+      | ptr |      | ptr |      | None|
                   +-----+      +-----+      +-----+

插入新元素后：

    +------+      +-----+      +-----+      +-----+
    | head |  ->  | data|  ->  | data|  ->  | new |
    +------+      | ptr |      | ptr |      | ptr |
                   +-----+      +-----+      | None|
                                            +-----+

2.2 代码实现

类似地，可以通过定义 Node 类和 LinkedList 类来实现添加元素到链表尾部的操作。

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

class LinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next

        curr_node.next = new_node

    def traverse(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

# Test the code
ll = LinkedList()
ll.add_to_end(1)
ll.add_to_end(2)
ll.add_to_end(3)
ll.traverse()

输出结果为：

1
2
3

2.3 示例说明

示例一

def test1():
    ll = LinkedList()
    ll.add_to_end('a')
    ll.add_to_end('b')
    ll.add_to_end('c')
    ll.traverse()

输出结果为：

a
b
c

示例二

def test2():
    ll = LinkedList()
    ll.add_to_end(1)
    ll.add_to_end(2)
    ll.add_to_end(3)
    ll.add_to_end(4)
    ll.add_to_end(5)
    ll.add_to_end(6)
    ll.traverse()

输出结果为：

1
2
3
4
5
6
Tags: