第2关:链表的实现之增删功能
时间: 2023-05-28 14:04:49 浏览: 138
链表是一种常见的数据结构,它由一个个节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。链表有很多操作,其中包括增加和删除节点。本关将介绍链表的增删功能的实现。
1. 增加节点
增加节点操作通常分为两种情况:在链表头部增加节点和在链表尾部增加节点。
在链表头部增加节点:
我们可以先创建一个新的节点,然后将其next指向原来的头节点,最后将新节点设置为头节点。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add_first(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
```
在链表尾部增加节点:
我们需要先遍历链表找到最后一个节点,然后将其next指向新节点。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add_last(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
```
2. 删除节点
删除节点操作通常也分为两种情况:删除头节点和删除尾节点。
删除头节点:
我们可以将头节点的下一个节点设置为新的头节点。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def remove_first(self):
if self.head is None:
return
self.head = self.head.next
```
删除尾节点:
我们需要遍历链表找到倒数第二个节点,然后将其next设置为None。
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def remove_last(self):
if self.head is None:
return
if self.head.next is None:
self.head = None
return
second_last = self.head
while second_last.next.next:
second_last = second_last.next
second_last.next = None
```
以上就是链表的增删功能的实现。注意,在实际应用中,还需要考虑更多情况,例如删除中间某个节点等。