链表的插入操作及时间复杂度分析

# 2.1 头插法

### 2.1.1 头插法的步骤

头插法是一种在链表头部插入新节点的操作。其步骤如下：

1. 创建一个新节点，并将其数据域赋值为待插入的数据。
2. 将新节点的 next 指针指向原链表的头部节点。
3. 将原链表的头部节点更新为新节点。

### 2.1.2 头插法的代码实现

def head_insert(head, data):
    """
    在链表头部插入新节点。

    参数：
        head: 链表头部节点
        data: 待插入的数据
    """
    new_node = Node(data)
    new_node.next = head
    head = new_node
    return head

# 2. 链表的插入操作

在链表中插入元素是一个常见的操作，它允许我们在链表的任何位置添加新元素。有三种基本类型的插入操作：头插法、尾插法和中间插入。

### 2.1 头插法

头插法是在链表的头部插入一个新元素。它是一种简单高效的操作，因为我们只需要更新头指针即可。

#### 2.1.1 头插法的步骤

1. 创建一个新的节点，并将其数据域设置为要插入的值。
2. 将新节点的 next 指针指向当前的头节点。
3. 将新节点设置为头节点。

#### 2.1.2 头插法的代码实现

def insert_at_head(self, value):
    """
    在链表头部插入一个元素

    参数：
        value: 要插入的值
    """
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

**代码逻辑分析：**

* 创建一个新的节点，并将其数据域设置为要插入的值。
* 将新节点的 next 指针指向当前的头节点。
* 将新节点设置为头节点。

### 2.2 尾插法

尾插法是在链表的尾部插入一个新元素。它比头插法复杂一些，因为我们需要遍历链表找到尾节点。

#### 2.2.1 尾插法的步骤

1. 创建一个新的节点，并将其数据域设置为要插入的值。
2. 如果链表为空，则将新节点设置为头节点。
3. 否则，遍历链表找到尾节点，并将新节点的 next 指针指向尾节点。
4. 将尾节点的 next 指针指向新节点。

#### 2.2.2 尾插法的代码实现

def insert_at_tail(self, value):
    """
    在链表尾部插入一个元素

    参数：
        value: 要插入的值
    """
    new_node = Node(value)
    if self.head is None:
        self.head = new_node
    else:
        current_node = self.head
        while current_node.next is not None:
            current_node = current_node.next
        current_node.next = new_node

**代码逻辑分析：**

* 创建一个新的节点，并将其数据域设置为要插入的值。
* 如果链表为空，则将新节点设置为头节点。
* 否则，遍历链表找到尾节点，并将新节点的 next 指针指向尾节点。
* 将尾节点的 next 指针指向新节点。

### 2.3 中间插入

中间插入是在链表的中间位置插入一个新元素。它比头插法和尾插法都复杂，因为我们需要找到要插入位置的前一个节点。

#### 2.3.1 中间插入的步骤

1. 创建一个新的节点，并将其数据域设置为要插入的值。
2. 如果要插入的位置是头节点，则使用头插法。
3. 如果要插入的位置是尾节点，则使用尾插法。
4. 否则，遍历链表找到要插入位置的前一个节点。
5. 将新节点的 next 指针指向要插入位置的前一个节点的 next 指针。
6. 将要插入位置的前一个节点的 next 指针指向新节点。

#### 2.3.2 中间插入的代码实现

def insert_at_index(self, index, value):
    """
    在链表指定位置插入一个元素

    参数：
        index: 要插入的位置
        value: 要插入的值
    """
    if index == 0:
        self.insert_at_head(value)
    elif index == self.get_length():
        self.insert_at_tail(value)
    else:
        new_node = Node(value)
        current_node = self.head
        for i in range(index - 1):
            current_node = current_node.next
        new_node.next = current_node.next
        current_node.next = new_node

**代码逻辑分析：**

* 如果要插入的位置是头节点，则使用头插法。
* 如果要插入的位置是尾节点，则使用尾插法。
* 否则，遍历链表找到要插入位置的前一个节点。
* 将新节点的 next 指针指向要插入位置的前一个节点的 next 指针。
* 将要插入位置