python版本单链表实现代码

让我来详细讲解一下“python版本单链表实现代码”的完整攻略。

1. 单链表介绍

单链表是一种数据结构，它由多个节点构成，每个节点包含数据和指向下一个节点的指针。单链表的特点是插入和删除的时间复杂度为O(1)，但访问的时间复杂度为O(n)。具体实现时，我们需要定义一个链表节点类Node和链表类LinkedList来表示单链表。

2. 链表节点类Node

链表节点类Node只包含两个属性，data和next，分别表示节点的数据和指向下一个节点的指针。代码如下：

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

3. 链表类LinkedList

链表类LinkedList包含两个属性，head和size，分别表示链表的头节点和链表的长度。代码如下：

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

链表类LinkedList还需要实现插入、删除、获取链表长度等操作。下面分别介绍这些操作的实现。

4. 插入节点

插入节点操作包含三个步骤：创建一个新的节点，将新节点的next指向当前节点的next，将当前节点的next指向新节点。代码如下：

def insert(self, data, index):
    if index < 0 or index > self.size:
        raise Exception("Index out of range")
    node = Node(data)
    if index == 0:
        node.next = self.head
        self.head = node
    else:
        p = self.head
        for i in range(index - 1):
            p = p.next
        node.next = p.next
        p.next = node
    self.size += 1

插入节点的示例：

linked_list = LinkedList()
linked_list.insert(1, 0)    # 在索引0处插入1
linked_list.insert(2, 1)    # 在索引1处插入2
linked_list.insert(3, 2)    # 在索引2处插入3
print(linked_list)          # 打印链表：1 -> 2 -> 3

5. 删除节点

删除节点操作也包含三个步骤：找到要删除的节点前一个节点，将前一个节点的next指向要删除节点的next，将要删除节点的next指向None。代码如下：

def remove(self, index):
    if index < 0 or index >= self.size:
        raise Exception("Index out of range")
    if index == 0:
        self.head = self.head.next
    else:
        p = self.head
        for i in range(index - 1):
            p = p.next
        p.next = p.next.next
    self.size -= 1

删除节点的示例：

linked_list = LinkedList()
linked_list.insert(1, 0)
linked_list.insert(2, 1)
linked_list.insert(3, 2)
linked_list.remove(1)       # 删除索引1处的节点
print(linked_list)          # 打印链表：1 -> 3

6. 获取节点

获取节点操作只需要循环遍历链表直到找到指定索引处的节点即可。代码如下：

def get(self, index):
    if index < 0 or index >= self.size:
        raise Exception("Index out of range")
    p = self.head
    for i in range(index):
        p = p.next
    return p.data

获取节点的示例：

linked_list = LinkedList()
linked_list.insert(1, 0)
linked_list.insert(2, 1)
linked_list.insert(3, 2)
print(linked_list.get(1))   # 输出1

以上就是“python版本单链表实现代码”的完整攻略，希望能对你有所帮助。