python数据结构-链表

python学习笔记

python学习笔记之链表

数据结构-链表

什么是链表，我对这个概念非常陌生。

链表是实现了数据之间保持逻辑顺序，但存储空间不必按顺序的方法。可以用一个图来表示这种链表的数据结构：

链表
　　　　　　　　　　　　　　　　图１：链表

链表中的基本要素：

  1. 结点(也可以叫节点或元素)，每一个结点有两个域，左边部份叫值域，用于存放用户数据；右边叫指针域，一般是存储着到下一个元素的指针
  2. head结点，head是一个特殊的结节，head结点永远指向第一个结点
  3. tail结点，tail结点也是一个特殊的结点，tail结点永远指向最后一个节点
  4. None，链表中最后一个结点指针域的指针指向None值，因也叫接地点，所以有些资料上用电气上的接地符号代表None

链表的常用方法：

  1. LinkedList() 创建空链表，不需要参数，返回值是空链表
  2. is_empty() 测试链表是否为空，不需要参数，返回值是布尔值
  3. append(data) 在尾部增加一个元素作为列表最后一个。参数是要追加的元素，无返回值
  4. iter() 遍历链表，无参数，无返回值，此方法一般是一个生成器
  5. insert(idx,value) 插入一个元素，参数为插入元素的索引和值
  6. remove(idx)移除1个元素，参数为要移除的元素或索引，并修改链表
  7. size() 返回链表的元素数，不需要参数，返回值是个整数
  8. search(item) 查找链表某元素，参数为要查找的元素或索引，返回是布尔值

节点类

python用类来实现链表的数据结构，节点（Node）是实现链表的基本模块，每个节点至少包括两个重要部分。首先，包括节点自身的数据，称为“数据域”(也叫值域)。其次，每个节点包括下一个节点的“引用”(也叫指针)

下边的代码用于实现一个Node类：

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

此节点类只有一个构建函数，接收一个数据参数，其中next表示指针域的指针，实例化后得到一个节点对象，如下：

1
node = Node(4)

此节点对象数据为4，指针指向None。

这样一个节点对象可以用一个图例来更形象的说明，如下：

链表
　　　　　　　　　　　　　　图2:　节点

链表类

先来看LinkedList类的构建函数：

1
2
3
4
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

此类实例后会生成一个链表对象，初始化了head和tail节点，且两节点都指向None，实例化代码如下：

1
link_list = LinkedList()

也可以用图形象的表示这个链表对象，如下：

链表
　　　　　　　　　　　　　　　　　　　图3：空链表

is_empty方法实现

is_empty方法检查链表是否是一个空链表，这个方法只需要检查head节点是否指向None即可，代码如下：

1
2
def is_empty(self):
        return self.head is None

如果是空列表返回True，否则返回False

append方法实现

append方法表示增加元素到链表，这和insert方法不同，前者使新增加的元素成为链表中第一个节点，而后者是根据索引值来判断插入到链表的哪个位置。代码如下：

1
2
3
4
5
6
7
8
def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

既然要新增加节点，首先把Node类实例化得到一个node对象。这里有两种情况需要考虑，一是链表是一个空链表时怎样append一个节点；二是当链表不是空链表时又怎样append一个节点？

当if self.head is None:为True时，把链表的head和tail都指向了node，假如我们执行了

1
link_list(append(4))

此时的链表结构如下图：

链表
　　　　　　　　　　　　　　　　图4：append-1

当if self.head is None:为False时,说明链表已经增加了一个节点了，再增加一个节点时head已经指向了第一个节点，所以不为None，比如增加的第二个节点为：

1
link_list(append(5))

增加第二个节点的操作需要分两步完成，第一步：self.tail.next = node，即把上一个节点的next指针指向当前node；第二步：self.tail = node，把tail移动到node，如下图：

链表

移动完成后就成这样了：

链表

当增加第三个、第四个等节点时，按照上边的操作依次类推。

iter方法实现

iter方法表示遍历链表。在遍历链表时也要首先考虑空链表的情况。遍历链表时从head开始，直到一个节点的next指向None结束，代码如下：

1
2
3
4
5
6
7
8
def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.data
        while cur.next:
            cur = cur.next
            yield cur.data

当是遍历一个空链表时，if not self.head:为True，直接返回None；如果不是空链表就让一个局部变量cur指向head,并把head的data属性yield出来，再对cur的next指针指向的对象做while循环，直到next指向None，这样就遍历了链表。

insert方法实现

假如采取append方法又增加了两个节点，增加完成后如下图：

链表

如果想在数据域为6的那节点处插入一个节点，需要做的操作有两步：

  1. 把新节点的next指针指向数据域为6的这个节点，即为数据域为5节点的next指向指向的对象
  2. 把数据域为5节点的next指针指向新加的节点

注： 这两个步骤不能颠倒，如果颠倒，数据域为6的节点会被丢失，数据域为7的节点不再是链表的节点。

示意图如下：

链表

还要额外考虑两种情况：

  1. 空链表时
  2. 插入位置超出链表节点的长度时
  3. 插入位置是链表的最后一个节点时，需要移动tail

当是在链表最后一个节点插入时，示意图如下：

链表

要在指定的索引位置插入一个节点，前提是需要找到这个位置，在链表中只有采用遍历的方式，具有O(n)的速度，最糟糕时会遍历链表的所有节点，而当找到插入点时，我们并不需要当前节点的信息，而是需要前一个节点的信息，所以代码中巧妙的使用了while cur_idx < idx-1:的方式，这样能使用cur这个变量能指向插入点上一个节点对象。

实现insert方法的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def insert(self, idx, value):
        cur = self.head
        cur_idx = 0
        if cur is None:
            raise Exception('The list is an empty list')
        while cur_idx < idx-1:
            cur = cur.next
            if cur is None:
                raise Exception('list length less than index')
            cur_idx += 1
        node = Node(value)
        node.next = cur.next
        cur.next = node
        if node.next is None:
            self.tail = node

remove方法实现

remove方法接收一个idx参数，表示要删除节点的索引，此方法要考虑以下几种情况：

  1. 空链表，直接抛出异常
  2. 删除第一个节点时，移动head到删除节点的next指针指向的对象
  3. 链表只有一个节点时，把head与tail都指向None即可
  4. 删除最后一个节点时，需要移动tail到上一个节点
  5. 遍历链表时要判断给定的索引是否大于链表的长度，如果大于则抛出异常信息

请看下边图例：

链表

链表

以下为remove函数的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def remove(self, idx):
       cur = self.head
       cur_idx = 0
       if self.head is None:  # 空链表时
           raise Exception('The list is an empty list')
       while cur_idx < idx-1:
           cur = cur.next
           if cur is None:
               raise Exception('list length less than index')
           cur_idx += 1
       if idx == 0:   # 当删除第一个节点时
           self.head = cur.next
           cur = cur.next
           return
       if self.head is self.tail:   # 当只有一个节点的链表时
           self.head = None
           self.tail = None
           return
       cur.next = cur.next.next
       if cur.next is None:  # 当删除的节点是链表最后一个节点时
           self.tail = cur

size函数实现

size函数不接收参数，返回链表中节点的个数，要获得链表的节点个数，必定会遍历链表，直到最后一个节点的next指针指向None时链表遍历完成，遍历时可以用一个累加器来计算节点的个数，如下代码：

1
2
3
4
5
6
7
8
9
def size(self):
        current = self.head
        count = 0
        if current is None:
            return 'The list is an empty list'
        while current is not None:
            count += 1
            current = current.next
        return count

search函数实现

search函数接收一个item参数，表示查找节点中数据域的值。search函数遍历链表，每到一个节点把当前节点的data值与item作比较，最糟糕的情况下会全遍历链表。如果查找到有些数据则返回True，否则返回False，代码如下：

1
2
3
4
5
6
7
8
9
def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.data == item:
                found = True
            else:
                current = current.next
        return found

Node类与LinkedList类完整代码

最后把Node类和LinkedList类的完整代码整理如下：

Node类：

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

LinkedList类及调度代码：

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
85
86
87
88
89
90
91
92
93
94
95
96
97
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
  
    def is_empty(self):
        return self.head is None
  
    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
  
    def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.data
        while cur.next:
            cur = cur.next
            yield cur.data
  
    def insert(self, idx, value):
        cur = self.head
        cur_idx = 0
        if cur is None:             # 判断是否是空链表
            raise Exception('The list is an empty list')
        while cur_idx < idx-1:   # 遍历链表
            cur = cur.next
            if cur is None:   # 判断是不是最后一个元素
                raise Exception('list length less than index')
            cur_idx += 1
        node = Node(value)
        node.next = cur.next
        cur.next = node
        if node.next is None:
            self.tail = node
  
    def remove(self, idx):
        cur = self.head
        cur_idx = 0
        if self.head is None:  # 空链表时
            raise Exception('The list is an empty list')
        while cur_idx < idx-1:
            cur = cur.next
            if cur is None:
                raise Exception('list length less than index')
            cur_idx += 1
        if idx == 0:   # 当删除第一个节点时
            self.head = cur.next
            cur = cur.next
            return
        if self.head is self.tail:   # 当只有一个节点的链表时
            self.head = None
            self.tail = None
            return
        cur.next = cur.next.next
        if cur.next is None:  # 当删除的节点是链表最后一个节点时
            self.tail = cur
  
    def size(self):
        current = self.head
        count = 0
        if current is None:
            return 'The list is an empty list'
        while current is not None:
            count += 1
            current = current.next
        return count
  
    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.data == item:
                found = True
            else:
                current = current.next
        return found
  
if __name__ == '__main__':
    link_list = LinkedList()
    for i in range(150):
        link_list.append(i)
#    print(link_list.is_empty())
#    link_list.insert(10, 30)
  
#    link_list.remove(0)
  
    for node in link_list.iter():
        print('node is {0}'.format(node))
    print(link_list.size())
#    print(link_list.search(20))

本文标题:python数据结构-链表

文章作者:

发布时间:2016-05-12, 20:00:00

最后更新:2020-08-08, 23:29:11

原始链接:http://zhaochj.github.io/2016/05/12/2016-05-12-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E9%93%BE%E8%A1%A8/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数据结构-链表
    1. 1.1. 节点类
    2. 1.2. 链表类
      1. 1.2.1. is_empty方法实现
      2. 1.2.2. append方法实现
    3. 1.3. iter方法实现
    4. 1.4. insert方法实现
    5. 1.5. remove方法实现
    6. 1.6. size函数实现
    7. 1.7. search函数实现
    8. 1.8. Node类与LinkedList类完整代码
|