单链表SinglyLinkedList

发表于 | 分类于 | 阅读次数 ℃
本文字数： 1.4k | 阅读时长 ≈ 1 分钟

链表通过“指针”将一组零散的内存块串联起来，所以它的底层结构是由两部分构成的：

  • 结点
    结点用来存储数据，可以是int、string等
  • 指针
    指针用来记录下一个结点的地址 根据指针与结点的指向关系可以细分链表的类型：单链表、双向链表、循环链表。
    本文用Python实现单链表的相关操作。

先构建链表的“核心单元”：Node类

1
2
3
4
5
6
7
#-*-coding:utf-8-*-

class Node(object):

    def __init__(self, data, next_node=None):
        self.data = data
        self._next = next_node

创建SinglyLinkedList类：

1
2
3
4
class SinglyLinkedList(object):

    def __init__(self):
        self._head = None

接下来具体的链表操作：

添加结点到头部

1
2
3
4
5
6
7
8
9
10
# 将待添加的值实例化成Node类
def change_value_to_node(self, value):
    new_node = Node(value)
    self.insert_node_to_head(new_node)

# 将新结点插入到最前面
def insert_node_to_head(self, new_node):
    if new_node:
        new_node._next = self._head
        self._head = new_node

在给定结点后添加新结点

1
2
3
def insert_node_after_target(self, node, new_node):
    new_node._next = node._next
    node._next = new_node

删除给定结点的后继结点

1
2
3
4
5
def delete_next_node_after_target(self, node):
    if node._next == None:
        return 
    else:
        node._next = node._next._next

删除当前给定的结点

1
2
3
4
5
6
def delete_current_node(self, node):
    p = self._head
    if p == node:
        self._head = p._next
    while p and p._next == node:
        p._next = p._next._next

返回给定值的结点信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 根据值查找
def find_by_value(self, value):
    p = self._head
    while p and p.data != value:
        p = p._next
    return p

# 类似于下标索引的查找
def find_by_index(self, index):
    p = self._head 
    position = 0
    while p and position != index:
        p = p._next
        position += 1
    return p