Contents

Python 实现单向链表

Contents

链表是一种物理存储单元上非连续、非顺序的存储结构, 数据元素的逻辑顺序是通过链表中的指针链接次序实现的.

链表的基本单位为 node

node 存储 data 和 next

data: 数据

next: 指向下一个 node 的指针

插入单位为 n 的数据 时间复杂度为 O(1)

查找单位为 n 的数据 时间复杂度为 O(n)

node

1
2
3
4
5
6
7
class Node(object):
    def __init__(self,data):
        self.data = data
        self.next = None

    def __repr__(self):
        return str(self.data)

链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class Link(object):
    def __init__(self,head=None):
        self.head = Node(head)
        if head:
            self.length = 1
        else:
            self.length = 0

    def __len__(self):
        return self.length

    def __str__(self):
        current = 0
        p = self.head
        item = '['
        while current <= self.length:
            item += ' ' + '\'' + str(p) + '\''
            p = p.next
            current += 1
        item += ' ]'
        return item

    def __call__(self):
        current = 0
        p = self.head
        while current <= self.length:
            yield p
            p = p.next
            current += 1
    
    def append(self,data):
        data = Node(data)
        if self.head == None:
            self.head = data
        else:
            p = self.head
            while p.next:
                p = p.next
            p.next,p.next.next = data,None
        self.length += 1

    def pop(self):
        p = self.head
        while p.next:
            p = p.next
            pp = p
        pp = None
        self.length -= 1       
    
    def insert(self,index,data):
        data = Node(data)
        if index == 0:
            p = self.head
            self.head = data
            self.head.next = p
        else:
            current = 0
            p = self.head
            while current <= self.length:
                if current +1 == index:
                    pp = p.next
                    p.next = data
                    p.next.next = pp
                    break
                else:
                    current += 1
                    p = p.next
        self.length += 1
    
    def delete(self,index):
        if index == 0:
            self.head = self.head.next
        else:
            current = 0
            p = self.head
            while current <= self.length:
                if current + 1 == index:
                    pp = p.next.next
                    p.next = pp
                    break
                else:
                    current += 1
                    p = p.next
        self.length -= 1