python的链表基础知识点

1. 链表的概念

链表是计算机中一种常用的数据结构，用于储存一系列的数据元素。与数组不同，链表中的元素在内存中不是连续存储的，而是通过链表中的指针链接起来的。

链表由一系列的节点（Node）组成，每个节点包含一个数据元素以及一个指向下一个节点的指针。链表的头节点指向第一个节点，尾节点的指针为空。

2. 单向链表

2.1 创建单向链表

在Python中，可以使用类来表示链表。首先，我们需要定义一个节点类，包含一个数据属性和一个指向下一个节点的指针属性。下面是一个简单的单向链表的代码示例：

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

2.2 遍历单向链表

遍历单向链表意味着访问链表中的每个节点，从头节点开始直到尾节点。可以使用一个循环来实现遍历操作。

下面是一个遍历单向链表的代码示例：

def traverse(self):
    current = self.head
    while current:
        print(current.data)
        current = current.next

上述代码中，我们使用一个循环来遍历链表。通过遍历，我们可以访问每个节点的数据属性，并将节点指针指向下一个节点。直到链表的尾节点为止。

3. 双向链表

双向链表与单向链表相似，但每个节点有两个指针，一个指向上一个节点，另一个指向下一个节点。

3.1 创建双向链表

与单向链表类似，我们需要定义一个节点类，包含数据和两个指针属性。

下面是一个简单的双向链表的代码示例：

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

双向链表中，需要同时维护链表的头节点和尾节点，用于执行插入和删除操作。

3.2 双向链表的插入和删除

双向链表相对于单向链表的一个优点是可以更方便地在任意位置插入和删除节点。

下面是一个在双向链表中插入节点的代码示例：

def insert(self, data, position):
    new_node = Node(data)
    if position == 0:
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
    else:
        current = self.head
        for _ in range(position - 1):
            current = current.next
        new_node.prev = current
        new_node.next = current.next
        if current.next:
            current.next.prev = new_node
        else:
            self.tail = new_node
        current.next = new_node

上述代码中，我们根据位置参数在双向链表中插入一个新节点。如果位置为0，则将新节点作为新的头节点，否则，我们遍历链表，找到位置指定的节点，并将新节点插入到其前面。

4. 总结

本文介绍了链表的基础知识点，包括单向链表和双向链表的创建、遍历、插入和删除操作。链表作为一种常用的数据结构，在计算机科学领域有着广泛的应用。通过学习链表的基础知识，可以帮助我们更好地理解和应用链表。