单链表_节点定义&单链表基本操作_普通链表的节点定义

链表的引入

链表

    顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不灵活。
    链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

链表的定义

    链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据集，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。

单向链表

   单向链表也叫做单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

1. 表元素域elem用来存放具体的数据
2. 链接域next用来存放下一个节点的位置（python中的标识）
3. 变量p指向链表的头节点位置，从p出发能找到表中的任意节点

【示例】节点实现

class Node(object):
	"""单链表的节点"""
	def __init__(self, elem):
		#item存放数据元素
		self.elem = elem
		#next是下一个节点的标识
		self.next = None
1
2
3
4
5
6
7

【示例】单链表实现

#构造单链表的节点
class Node(object):
    def __init__(self,elem):
        #elem指数据元素
        self.elem = elem
        #指向下一个节点的链接域
        self.next = None

#构造单向链表类
class SingleLinkList:
    #单项链表初始化方法
    def __init__(self, node=None):
        #判断node是否为空
        if node != None:
            headNode = Node(node)
            self.__head = headNode
        else:
            self.__head = node
    
    #遍历链表
    def travel(self):
        curNode = self.__head
        while curNode != None:
            print(curNode.elem, end = '\t')
            curNode = curNode.next
        print('')

    #在头部添加元素
    def add(self, item):
        #将传入的值构造成节点
        node = Node(item)
        #将新节点的链接域指向头节点
        node.next = self.__head
        #将链表的头head指向新节点
        self.__head = node
    
    #在单向链表尾部追加元素
    def append(self, item):
        #将传入的值构造成节点
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:#单链表不为空
            curNode = self.__head
            while curNode.next != None:
                curNode = curNode.next
            #修改最后一个节点的next指向新增节点node
            curNode.next = node

    #在指定位置添加元素(考虑三种情况)
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        #找到指定位置
        else:
            node = Node(item)
            preNode = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                preNode = preNode.next
            #先将新节点node的next指向插入位置的节点
            node.next = preNode.next
            #将插入位置的前一个节点的next指向新节点
            preNode.next = node 

    #删除节点
    def remove(self, item):
        curNode = self.__head
        preNode = None
        while curNode != None:
            if curNode.elem == item:
                #判断是否是头节点
                if preNode == None:
                    #头节点指向当前节点的next
                    self.__head = curNode.next
                else:
                    #删除
                    preNode.next = curNode.next
                break
            else:
                preNode = curNode
                curNode = curNode.next

    #查找节点是否存在
    def search(self, item):
        curNode = self.__head
        while curNode != None:
            if curNode.elem == item:
                return True
            curNode = curNode.next
        return False

    #判断当前链表是否为空
    def is_empty(self):
        #判断head指向是否是None，若是则为空链表
        return self.__head == None

    #计算单向链表的长度
    def length(self):
        #计算节点，有几个节点长度就是多少
        count = 0
        curNode = self.__head
        while curNode != None:
            count += 1
            curNode = curNode.next
        return count

if __name__=='__main__':
    #初始化元素值为20的单项链表
    singlelinklist = SingleLinkList(20)
    print('是否为空链表',singlelinklist.is_empty())
    print('链表的长度',singlelinklist.length())
    print('---------链表遍历---------')
    singlelinklist.travel()
    print('-----------查找-----------')
    print(singlelinklist.search(20))
    print('--------头部插入--------')
    singlelinklist.add(1)
    singlelinklist.add(2)
    singlelinklist.add(3)
    singlelinklist.travel()
    print('---------尾部追加--------')
    singlelinklist.append(10)
    singlelinklist.append(20)
    singlelinklist.append(30)
    singlelinklist.travel()
    print('-------任意位置插入-------')
    singlelinklist.insert(2,100)
    singlelinklist.travel()
    print('--------删除节点-------')
    singlelinklist.remove(100)
    singlelinklist.travel()
    singlelinklist.remove(1)
    singlelinklist.travel()
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

【示例】单链表实现_执行结果