单链表

单链表是一种链式的数据结构，链表中的数据用结点来表示，每个结点由：数据元素和指向下一个数据元素的指针组成，指针就是连接每个结点的地址。

说白了：单链表就是由很多个结点组成，每个结点之间用指针连接着，从前驱节点指向后继结点。

（这里所说的指针只是一个虚拟的指代，并非像c语言中的指针）

以下是创建一个单链表并实现一些功能的实例，先分布详解每个函数，最后再给出完整代码

首先创建一个结点类

里面包含数据元素和指向下一个数据元素的指针

class Node(object):

"""创建单个结点类"""

def __init__(self, data):

self.data = data

self.next = None

然后创建一个单链表的类

里面包含一些功能，接下来写的函数都是包含在这个类中的。

在创建单链表这个类中，我们先写一个初始化函数，用来初始化一个头结点

然后再写一个函数，判断这个链表是否为空，如果为空，就返回True

class SingleLinkedList(object):

"""创建一个单链表"""

def __init__(self):

self.head = None

def is_empty(self):

"""判断链表是否为空"""

return self.head is None

创建一个获取单链表长度的函数

cur 英文为current，意为：现在的，表示当前指针所指向的结点，这里从头结点开始

count就是链表的长度，当这个结点不为空的时候，长度就加一，然后当前指针所指向的结点(cur)向后移，就是将cur的下一个变为cur。

def length(self):

"""获取链表的长度"""

cur = self.head

count = 0

while cur is not None:

count += 1

cur = cur.next

return count

在链表的头部添加元素

首先我们需要创建一个新结点，然后令这个结点的指针指向原来链表的头部结点，再将头部结点(head)这个称号给这个新结点，这样，这个新结点就是新的头部结点了。

def add_fist(self, data):

"""在链表的头部添加元素"""

node = Node(data)

node.next = self.head

self.head = node

在链表的尾部添加元素

这次我们需要考虑两种情况：链表为空、链表不为空

当链表为空的时候，我们只能将这个新结点插入到头结点的位置

当链表不为空的时候，我们就需要将指针移动到链表的最后，然后将新结点插入到最后那一个结点的下一个位置，也就是添加到最后。

def add_last(self, data):

"""在链表的尾部添加元素"""

node = Node(data)

if self.is_empty():

self.head = node

else:

cur = self.head

while cur.next is not None:

cur = cur.next

cur.next = node

在链表的指定位置添加元素

这个函数我们使用的时候，需要指定index：元素在链表中的位置，data：元素的数据

我这里考虑了四种情况：出错情况、插入到头部的情况、插入到尾部的情况、插入到中间的情况

出错情况：当指定的索引小于零，或者大于这个链表的长度的时候，那肯定是没有这个位置的，所以判为出错

插入到头部的情况：当索引为0时，就是插入到链表的最前面，我们上面已经写过这个函数，所以直接调用就行了。

插入到尾部的情况：当索引为链表的长度时，就是插入到链表的最后面，所以也是直接调用就可以

插入到中间的情况：这种情况就不是特殊情况了，所以需要一个count来计数，让指针移动到待添加位置index的前一个位置，然后进行插入。中心思想就是，新结点 指向 原来指针指向的结点cur的后继结点，指针指向的结点cur指向新结点。

（有人可能想问，一定需要分出那么多种情况吗，有没有其它更简洁一点的方法？答案是：有的，这只是其中一种方法，使用其它方法也可以完成这个功能）

def insert_node(self, index, data):

"""在指定位置添加元素"""

node = Node(data)

if index < 0 or index > self.length():

return False

elif index == 0:

self.add_fist()

elif index == self.length():

self.add_last()

else:

cur = self.head

count = 0

while count < index - 1:

cur = cur.next

count += 1

node.next = cur.next

cur.next = node

删除指定结点

这里分了两种情况：删除的结点就是头结点、删除的结点不是头结点

删除的结点是头结点：这种情况就直接将头结点的称号给头结点的后继结点就可以了

删除的结点不是头结点：这种情况就需要逐步移动指针，进行查找了，直到找到那个要删除的元素。我们需要两个结点：指针指向的结点（当前查找的结点）、它的前驱节点

因为cur代表当前结点，pre代表它的前驱结点，所以初始化的时候，cur指向头结点，但头结点没有前驱结点了，所以初始化为None。然后在向后移动的时候，就可以进行交换赋值了。

最后我们找到了那个要删除的结点，也就是cur当前指向的，所以我们只需将它的前驱结点pre指向它的后继结点cur.next，这样就跳过了中间的那个结点cur，由此完成了删除操作。

def remove_node(self, data):

"""删除指定结点"""

cur = self.head # 指针指向的结点

pre = None # 指针指向结点的前一个

if self.head == data:

self.head.next = self.head

else:

while cur.data is not data:

pre = cur

cur = cur.next

pre.next = cur.next

查找指定结点是否存在

同删除操作相似，我们只需不断向后查找（cur = cur.next），找到那个要查找的结点为止。

def search_node_is_exist(self, data):

"""查找指定结点是否存在"""

cur = self.head

while cur is not None:

if cur.data == data:

return True

else:

cur = cur.next

return False

遍历并打印整个链表

不断的向后查找，将查找到的每个结点打印出来

def traversal(self):

"""遍历整个链表"""

cur = self.head

while cur is not None:

print(cur.data)

cur = cur.next

主函数进行测试

对上面的函数进行调用

if __name__ == '__main__':

lists = SingleLinkedList()

lists.add_fist(2)

lists.add_fist(1)

lists.add_last(4)

lists.insert_node(2, 3)

lists.traversal()

print(lists.is_empty())

print(lists.length())

lists.remove_node(4)

print(lists.search_node_is_exist(3))

lists.traversal()

输出结果截图

完整代码

class Node(object):

"""创建单个结点类"""

def __init__(self, data):

self.data = data

self.next = None

class SingleLinkedList(object):

"""创建一个单链表"""

def __init__(self):

self.head = None

def is_empty(self):

"""判断链表是否为空"""

return self.head is None

def length(self):

"""获取链表的长度"""

cur = self.head

count = 0

while cur is not None:

count += 1

cur = cur.next

return count

def add_fist(self, data):

"""在链表的头部添加元素"""

node = Node(data)

node.next = self.head

self.head = node

def add_last(self, data):

"""在链表的尾部添加元素"""

node = Node(data)

if self.is_empty():

self.head = node

else:

cur = self.head

while cur.next is not None:

cur = cur.next

cur.next = node

def insert_node(self, index, data):

"""在指定位置添加元素"""

node = Node(data)

if index < 0 or index > self.length():

return False

elif index == 0:

self.add_fist()

elif index == self.length():

self.add_last()

else:

cur = self.head

count = 0

while count < index - 1:

cur = cur.next

count += 1

node.next = cur.next

cur.next = node

def remove_node(self, data):

"""删除指定结点"""

cur = self.head # 指针指向的结点

pre = None # 指针指向结点的前一个

if self.head == data:

self.head.next = self.head

else:

while cur.data is not data:

pre = cur

cur = cur.next

pre.next = cur.next

def search_node_is_exist(self, data):

"""查找指定结点是否存在"""

cur = self.head

while cur is not None:

if cur.data == data:

return True

else:

cur = cur.next

return False

def traversal(self):

"""遍历整个链表"""

cur = self.head

while cur is not None:

print(cur.data)

cur = cur.next

if __name__ == '__main__':

lists = SingleLinkedList()

lists.add_fist(2)

lists.add_fist(1)

lists.add_last(4)

lists.insert_node(2, 3)

lists.traversal()

print(lists.is_empty())

print(lists.length())

lists.remove_node(4)

print(lists.search_node_is_exist(3))

lists.traversal()

上面这些函数的方法都比较简单，后续还会接触到更深一些的算法，但只要耐心学，并自己动手练习，再去找一些实例深入练习，就完全不是什么问题。