链表中插入节点

简介: 链表中插入节点

在链表中插入节点是一个常见的操作,特别是在处理动态数据时。在单向链表中,我们可以在链表的开头(头部)、结尾(尾部)或指定位置插入新节点。以下是关于如何在Python中的单向链表中插入节点的详细解释和代码实现:

一、引言

链表是一种常见的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。与数组相比,链表在插入和删除操作上具有更高的灵活性,因为链表不需要预先分配连续的内存空间。在链表中插入节点时,我们需要确定插入的位置,并相应地更新节点的指针。

二、插入节点的类型

头部插入(Head Insertion):在链表的开头插入新节点。这种插入方式的时间复杂度为O(1),因为无论链表有多长,我们总是可以直接访问到头部节点。

尾部插入(Tail Insertion):在链表的结尾插入新节点。这种插入方式需要遍历链表直到找到尾部节点,因此时间复杂度为O(n),其中n是链表的长度。

指定位置插入(Indexed Insertion):在链表的指定位置插入新节点。这种插入方式需要遍历链表直到找到指定位置的前一个节点,因此时间复杂度也是O(n)。

 

三、代码实现

1. 节点类(Node)

首先,我们需要定义一个节点类,用于表示链表中的每个节点。节点类通常包含两个属性:一个用于存储数据的数据字段和一个用于指向下一个节点的指针字段。

python复制代码

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

2. 链表类(LinkedList)

接下来,我们定义一个链表类,用于表示整个链表。链表类包含一个指向头节点的指针(head),以及一系列用于操作链表的方法(如头部插入、尾部插入和指定位置插入等)。

python复制代码

  class LinkedList: 
  def __init__(self): 
  self.head = None 
  
  # 头部插入 
  def insert_at_head(self, data): 
  new_node = Node(data) 
  if not self.head: 
  self.head = new_node 
  else: 
  new_node.next = self.head 
  self.head = new_node 
  
  # 尾部插入 
  def insert_at_tail(self, data): 
  new_node = Node(data) 
  if not self.head: 
  self.head = new_node 
  return 
  
  current = self.head 
  while current.next: 
  current = current.next 
  
  current.next = new_node 
  
  # 指定位置插入 
  def insert_at_index(self, index, data): 
  if index < 0: 
  raise IndexError("Negative index") 
  
  new_node = Node(data) 
  if index == 0: 
  self.insert_at_head(data) 
  return 
  
  current = self.head 
  current_index = 0 
  while current and current_index < index - 1: 
  current = current.next 
  current_index += 1 
  
  if not current: 
  raise IndexError("Index out of range") 
  
  new_node.next = current.next 
  current.next = new_node 
  
  # 遍历链表并显示节点数据 
  def display(self): 
  elements = [] 
  current_node = self.head 
  while current_node: 
  elements.append(current_node.data) 
  current_node = current_node.next 
  print(elements) 
  
  # 使用链表 
  linked_list = LinkedList() 
  linked_list.insert_at_head(1) 
  linked_list.insert_at_tail(2) 
  linked_list.insert_at_index(1, 3) 
  linked_list.display() # 输出: [1, 3, 2]

四、插入节点操作的详细解析

头部插入(insert_at_head

·创建一个新节点new_node,并将其数据字段设置为要插入的数据。

·如果链表为空(即headNone),则将新节点设置为头节点。

·否则,将新节点的next指针指向当前的头节点,并将头节点指向新节点。这样,新节点就成为了新的头节点。

尾部插入(Tail Insertion):在链表的结尾插入新节点。这种插入方式需要遍历链表直到找到尾部节点,因此时间复杂度为O(n),其中n是链表的长度。

指定位置插入(Indexed Insertion):在链表的指定位置插入新节点。这种插入方式需要遍历链表直到找到指定位置的前一个节点,因此时间复杂度也是O(n)。

相关文章
|
2月前
|
算法
【优选算法专栏】专题九:链表--------两两交换链表中的节点
【优选算法专栏】专题九:链表--------两两交换链表中的节点
26 0
|
2月前
|
存储 Python
删除链表节点详解
删除链表节点详解
|
29天前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
2月前
|
存储 Python
链表中删除节点
链表中删除节点
|
2月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
41 6
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
32 1
|
1月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
1月前
|
存储
删除链表的节点
删除链表的节点
16 0
|
1月前
|
存储 SQL 算法
|
1月前
|
SQL 算法 数据挖掘
力扣题目 19:删除链表的倒数第N个节点 【python】
力扣题目 19:删除链表的倒数第N个节点 【python】