2 单链表

1
# 在指定位置添加元素
2
def insert_node(self, index, data):
3
    node = Node(data)
4
    if index < 0 or index > self.length():
5
        return False
6
    elif index == 0:
7
        self.add_fist()
8
    elif index == self.length():
9
        self.add_last()
10
    else:
11
        cur = self.head
12
        count = 0
13
        while count < (index - 1):
14
            count += 1
15
            cur = cur.next
16
        # 退出循环的时候，cur指向index的前一个位置
17
        node.next = cur.next
18
        cur.next = node

1
#!usr/bin/env python
2
# encoding:utf-8
3

4
# 节点类
5
class Node(object):
6

7
    # 单个节点 初始化 输入一个值data，将值变为一个节点
8
    def __init__(self, data):
9
        self.data = data
10
        self.next = None
11

12
    # 打印对象中具体的属性值
13
    def __str__(self):
14
        # 测试基本功能，输出data
15
        return self.data
16

17

18
class SingleLinkedList(object):
19

20
    # 创建一个单链表
21
    def __init__(self):
22
        self.head = None
23

24
    # 判断链表是否为空
25
    def is_empty(self):
26
        return self.head is None
27

28
    # 获取链表的长度
29
    def length(self):
30
        cur = self.head
31
        count = 0
32
        while cur is not None:
33
            count += 1
34
            cur = cur.next
35
        return count
36

37
    # 头部添加元素
38
    def add_fist(self, data):
39
        node = Node(data)
40
        node.next = self.head
41
        self.head = node
42

43
    # 尾部添加元素
44
    def add_last(self, data):
45
        node = Node(data)
46
        # 如果链表为空，需要特殊处理
47
        if self.is_empty():
48
            self.head = node
49
        else:
50
            cur = self.head
51
            while cur.next is not None:
52
                cur = cur.next
53
            # 退出循环的时候，curl指向尾结点
54
            cur.next = node
55

56
    # 在指定位置添加元素
57
    def insert_node(self, index, data):
58
        node = Node(data)
59
        if index < 0 or index > self.length():
60
            return False
61
        elif index == 0:
62
            self.add_fist()
63
        elif index == self.length():
64
            self.add_last()
65
        else:
66
            cur = self.head
67
            count = 0
68
            while count < (index - 1):
69
                count += 1
70
                cur = cur.next
71
            # 退出循环的时候，cur指向index的前一个位置
72
            node.next = cur.next
73
            cur.next = node
74

75
    # 删除指定节点
76
    def remove_node(self, data):
77
        cur = self.head  # 指针指向的结点
78
        pre = None  # 指针指向结点的前一个
79
        if self.head == data:
80
            self.head.next = self.head
81
        else:
82
            while cur.data is not data:
83
                # 不是要找的元素，移动游标
84
                pre = cur
85
                cur = cur.next
86
            pre.next = cur.next
87

88
    # 查找节点
89
    def search_node(self, data):
90
        cur = self.head
91
        while cur is not None:
92
            if cur.data == data:
93
                return True
94
            else:
95
                cur = cur.next
96
        return False
97

98
    # 遍历 打印链表
99
    def traverse_to_print_node(self):
100
        # cur = self.head
101
        # while cur is not None:
102
        #     print(cur.data, end = " ")
103
        #     cur = cur.next
104
        print_list = []
105
        cur = self.head
106
        while cur is not None:
107
            print_list.append(str(cur.data))
108
            cur = cur.next
109
        print('->'.join(print_list))
110

111
# 测试
112
if __name__ == '__main__':
113
    list = SingleLinkedList()
114
    list.add_fist(2)
115
    list.add_fist(1)
116
    list.add_last(4)
117
    list.insert_node(2, 3)
118
    list.traverse_to_print_node()
119
    print(list.is_empty())
120
    print(list.length())
121
    list.remove_node(4)
122
    print(list.search_node(3))
123
    list.traverse_to_print_node()