python链表节点的插入和删除
时间: 2023-11-11 14:03:11 浏览: 50
链表节点的插入和删除是链表操作中的两个重要部分。链表节点的插入可以分为在链表头部插入、在链表尾部插入和在链表中间插入三种情况。链表节点的删除可以分为删除链表头部节点、删除链表尾部节点和删除链表中间节点三种情况。
链表节点的插入:
1. 在链表头部插入节点:将新节点的next指向原链表的头节点,再将新节点设置为链表的头节点。
2. 在链表尾部插入节点:遍历链表找到尾节点,将尾节点的next指向新节点。
3. 在链表中间插入节点:遍历链表找到要插入位置的前一个节点,将前一个节点的next指向新节点,新节点的next指向原来的后一个节点。
链表节点的删除:
1. 删除链表头部节点:将链表的头节点指向原头节点的下一个节点。
2. 删除链表尾部节点:遍历链表找到尾节点的前一个节点,将前一个节点的next指向None。
3. 删除链表中间节点:遍历链表找到要删除的节点的前一个节点,将前一个节点的next指向要删除节点的下一个节点。
相关问题
线性链表的插入和删除
线性链表的插入和删除操作如下所示:
1. 插入操作[^1]:
```python
# 在指定位置插入节点
def insertNode(head, position, value):
# 创建新节点
newNode = LinkNode(value)
# 找到插入位置的前一个节点
preNode = head
for i in range(position-1):
preNode = preNode.next
# 将新节点插入到链表中
newNode.next = preNode.next
preNode.next = newNode
# 示例
# 创建链表
head = LinkNode(None)
node1 = LinkNode(1)
node2 = LinkNode(2)
node3 = LinkNode(3)
head.next = node1
node1.next = node2
node2.next = node3
# 在第二个位置插入节点4
insertNode(head, 2, 4)
```
2. 删除操作:
```python
# 删除指定位置的节点
def deleteNode(head, position):
# 找到要删除节点的前一个节点
preNode = head
for i in range(position-1):
preNode = preNode.next
# 删除节点
deleteNode = preNode.next
preNode.next = deleteNode.next
deleteNode.next = None
# 示例
# 创建链表
head = LinkNode(None)
node1 = LinkNode(1)
node2 = LinkNode(2)
node3 = LinkNode(3)
head.next = node1
node1.next = node2
node2.next = node3
# 删除第二个位置的节点
deleteNode(head, 2)
```
双向链表的插入和删除代码
1. 双向链表的插入代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
def insertAfter(self, prev_node, new_data):
if prev_node is None:
return
new_node = Node(new_data)
new_node.next = prev_node.next
prev_node.next = new_node
new_node.prev = prev_node
if new_node.next is not None:
new_node.next.prev = new_node
def append(self, new_data):
new_node = Node(new_data)
new_node.next = None
if self.head is None:
new_node.prev = None
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
new_node.prev = last
return
def printList(self, node):
while node is not None:
print(node.data),
node = node.next
```
上述代码中,DoublyLinkedList类有三种插入方式,分别是push(), insertAfter()和append()方法,分别用于在链表头部、指定节点后和链表尾部插入节点。
2. 双向链表的删除代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
def deleteNode(self, dele):
if self.head is None or dele is None:
return
if self.head == dele:
self.head = dele.next
if dele.next is not None:
dele.next.prev = dele.prev
if dele.prev is not None:
dele.prev.next = dele.next
def printList(self, node):
while node is not None:
print(node.data),
node = node.next
```
上述代码中,DoublyLinkedList类有一个deleteNode()方法,用于删除指定节点。通过该方法实现双向链表的删除操作。