链表定义与实例

[TOC]

链表 定义：

  • 采用链表实现无序表
    • 为了实现无序表数据结构， 可以采用链接表的方案。
  • 虽然列表数据结构要求保持数据项的前后相对位置， 但这种前后位置的保持， 并不要求数据项依次存放在连续的存储空间
  • 采用链表实现无序表
    • 如下图， 数据项存放位置并没有规则， 但如果在数据项之间建立链接指向， 就可以保持其-前后相对位置第一个和最后一个数据项需要显式标记出来，一个是队首，一个是队尾，后面再无数据了。

链表实现：节点Node

  • 链表实现的最基本元素是节点Node,每个节点至少要包含2个信息： 数据项本身，以及指向下一个节点的引用信息,注意next为None的意义是没有下一个节点了，这个很重要 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

链表实现：无序表UnorderedList

  • 所以无序表必须要有对第一个节点的引用信息，设立一个属性head，保存对第一个节点的引用空表的head为None
  • 随着数据项的加入， 无序表的head始终，指向链条中的第一个节点，注意！无序表mylist对象本身并不包含数据项（数据项在节点中）其中包含的head只是对首个节点Node的引用,判断空表的isEmpty()很容易实现
  • 接下来， 考虑如何实现向无序表中添加数据项， 实现add方法。
    • 由于无序表并没有限定数据项之间的顺序
    • 新数据项可以加入到原表的任何位置
    • 按照实现的性能考虑， 应添加到最容易加入的位置上。
    • 要访问到整条链上的所有数据项
    • 都必须从表头head开始沿着next链接逐个向后查找
    • 所以添加新数据项最快捷的位置是表头，整个链表的首位置。
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
class UnorderedList:

    def __init__(self):
        self.head = None
	# 设立一个属性head，保存对第一个节点的引用空表的head为None 
    def isEmpty(self):
        return self.head == None
	# 添加新数据项最快捷的位置是表头，整个链表的首位置        
    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
	# 从链条头head开始遍历到表尾同时用变量累加经过的节点个数。
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count
    #从链表头head开始遍历到表尾， 同时判断当前节点的数据项是否目标
    def search(self,item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()

        return found
    # 首先要找到item， 这个过程跟search一样， 但在删除节点时， 需要current指向的是当前匹配数据项的节点而删除需要把前一个节点的next指向current的下一个节点所以在search current的同时，还要维护前一个(previous)节点的引用
    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

有序表OrderedList

  • 有序表是一种数据项依照其某可比性质（如整数大小、 字母表先后） 来决定在列表中的位置，越“小”的数据项越靠近列表的头， 越靠“前”

  • 在实现有序表的时候， 需要记住的是， 数据项的相对位置， 取决于它们之间的“大小”比较由于Python的扩展性，下面对数据项的讨论并不仅适用于整数，可适用于所有定义了__gt__方法（即’>’操作符）的数据类型

  • 对于isEmpty/size/remove这些方法，与 节 点 的 次 序 无 关 ， 所 以 其 实 现 跟
    UnorderedList 是一样的。 

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
class OrderedList:
    # OrderedList也设置一个head来保存链表表头的引用
    def __init__(self):
        self.head = None
	# 利用链表节点有序排列的特性， 来为search节省不存在数据项的查找时间一旦当前节点的数据项大于所要查找的数据项，则说明链表后面已经不可能再有要查找的数据项，可以直接返回False
    def search(self,item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()

        return found
     # add方法必须保证加入的数据项添加在合适的位置， 以维护整个链表的有序性
     # 引入一个previous的引用， 跟随当前节点current
    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()

        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)       
            
    def isEmpty(self):
        return self.head == None

    def length(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

        return count
    # 遍历链表
    def traverse(self):
        current = self.head
        while current != None:
            print(current.getData(),end="->")
            current = current.getNext()