入门单链表

链表简介

链表（linked list）作为一种常见的数据结构，通常由数据和指针组合而成。在一些没有指针结构的程序语言中，如 python、java等,指针被引用所代替。链表中的每个节点通过指针或引用相连接，你可以通过指针或者引用来遍历节点。

下图为单个节点的构成：

图片1.png

链表也有很多种形式，有单链表、循环链表、双向链表，下面我们介绍一种常用的单链表：

[图片上传失败...(image-23bd71-1547045843350)]

在单链表中，每个节点包括指向下一个节点的指针。但是单链表的首尾节点却特立独行，头结点只有指针，却没有数据；尾节点恰好相反，只有数据，没有指针，也就是提示我们链表后面不再有其他的节点。当我们找到第一个节点的时候，我们可以很轻松的获取链表其余节点。

这就像小时候玩游戏，一群小伙伴排成一排，手拉着手。左手被别人握紧，右手也紧紧握住别人的左手。左手就代表数据，右手代表指针。从第一个同学开始，这种通过左右手建立的联系，使我们很轻松的就找到了每一个人的位置。如果有一个小伙伴要加入，他会被分配在自己最好的朋友的前面，姑且将其记作“友人A”，我们就从第一个小伙伴开始遍历，如果找到了一个右手握住“友人A”的同学，姑且记作“同学B”，我们就停下来。先让这个小伙伴紧紧抓住“友人A”的右手，再让“同学B”握住他的左手。这样，这位小伙伴就找了自己的归宿。如果走遍了这条长长的队伍，还有没有找到属于自己的联系，那就稍稍有些寂寞了。如果有的人最好的”朋友C”变心了，他要出局了。我们还是要从第一个人开始遍历这条长长的队伍，一旦我们找到这个人前面的“同学D”，让“同学D”握住”朋友C“的手，然后再断开这个人与”朋友C“之间的羁绊，这个人重又恢复了自由身，尽管有少许的寂寞。

<span style=color:red>下面我们用 python 实现简单的单链表：</span>

创建一个节点

建立一个节点很简单，我们只要给节点对象的数据和指针属性赋值即可。头结点和尾节点稍稍有些不同，头结点数据为 None，尾节点指针为 None。

拿上面的例子说，就是没有人握住第一个小朋友的左手，所以说他的数据为空；最后一个小朋友也无法握住别人的左手，所以说他的指向为空。而其他小朋友，左手被别人紧紧握住，右手则紧紧握住别人，即数据与指向都不为空。

class Node(object):
    def __init__(self, data, pointer):
        self.data = data
        self.next = pointer

# 构建了只有首尾结点的链表
node = Node(12,None)
head = Node(None,node)

创建单链表

图片2.png

创建链表，就是在链表的尾部增加一个新的尾节点。首先要创建一个新的尾节点，代码为node = Node(value,None)。其次将前面的节点tail指向新创建的尾节点，即 tail的next属性要指向新创建的节点，代码为 tail.next = node。

形象点说，要想在那条队伍后面再加上一个小朋友，只要让末尾的握住新来的左手，那么这条队伍就增加了一名成员。

图片3.png

class SingleLinkedList(object):
    def __init__(self):
        self.head = Node(None, None)
        self.point = self.head
        
    def append(self, data):
        # 末尾追加节点
        new_node = Node(data, None)
        self.point.next = new_node
        self.point = new_node

插入节点

在特定节点前面插入数据：新建一个节点，然后找到特定节点的前驱结点，然后让新节点的next指向特定节点，而前驱结点也要指向新节点。

但是有些新来的人不甘心站在队伍的末尾，因为末尾的人没有”珍贵之物“（右手没有紧紧握住的对象），他想在队伍中找到命中之人。他就从头一个一个的寻找，直到发现有一个人握住了他的意中人。他就握住意中人的左手，再让前一个人握住他的左手。

def insert(self, data, find):
    # 插入数据(前向插入数据)
    if not self.head.next:
        print('链表为空')
        return None
    new_node = Node(data, None)
    self.point = self.head
    while self.point.next.data != find:
        self.point = self.point.next
        if self.point.next is None:
            print('没有找到该元素')
            return None

    new_node.next = self.point.next
    self.point.next = new_node

头后插节点

head 节点之后插入节点，如果 head 后没有节点，那么就直接让 head 节点指向新建节点；否则的话，就让新节点指向 head 后一个节点，而 head 再指向新节点。

形象点说，如果第一个人就孤零零的站着，就直接握住新朋友的手就好了。如果第一个人已经有朋友了，就让新朋友握住他的旧朋友的手，他再顺势握住新朋友的手。

def insert_after_head(self, data):
    node = Node(data, None)
    if not self.head.next:
        self.head.next = node
        return None
    node.next = self.head.next
    self.head.next = node

删除节点

我们从单链表头部开始遍历，先找到要删除节点的前置节点 p，再新建一个节点 q 指向要删除节点，接着将 p 节点指向要删除节点的下一个节点，最后将 q 节点删除。

形象地说，在队伍中找到这个被”抛弃”之人，让他前面的人撇开他，接着握住他后面的人的左手。然后这个稍微有些可怜的人就被系统判定“出局了”。

 def delete(self, find):
        # 删除节点
        # 判断是否为空链表
        if not self.head.next:
            print('链表为空')
            return None
        self.point = self.head
        while self.point.next.data != find:
            self.point = self.point.next
        pointer = self.point.next
        self.point.next = self.point.next.next
        del pointer

数据排序

这个长长的队伍要开始按照身高次序排序了，高个子在后，矮个子在前，即升序的顺序。从第一个人开始，依次问右手边的人，“我比你高吗？”，如果是的话，两个人就交换位置，这一轮下来，最高的人站在了队伍的最后。也就是说，至少有一个人的位置已经确定。紧接着，我们再开始同样的游戏，但这次我们只需要到倒数第二个人就好了，因为已经确定一个人的顺序了。当然如果有一轮下来，我们发现没有人交换位置，说明大家已经按照高矮排好了顺序，就可以结束游戏了。

def sort(self):
    # get_size()改变了 self.point 的指向
    length = self.get_size()
    i, j = 0, 0
    flag = 1
    while i < length:
        self.point = self.head.next
        while j < length - i - 1:
            if self.point.data > self.point.next.data:
                temp = self.point.data
                self.point.data = self.point.next.data
                self.point.next.data = temp
            self.point = self.point.next
            j += 1
            flag = 0
        if flag:
            break
        i += 1
        j = 0

求中间节点 只允许遍历一次

如果可以多次遍历的话，我们大可以求出链表的大小，再算出中间节点。但只让遍历一次的话，我们就要用到快慢指针的方法了。形象地说，就是有两个同学在操场上跑步，记为A,B。A 同学跑步速度是 B 同学的二倍，也就是说，A 同学跑完一圈的时候，B 同学刚好跑完半圈。同理，我们用快慢指针来遍历链表，快指针到达尾节点时，慢指针正好指向了中间节点。 代码中体现为，快指针每次前进两个节点，而慢指针只前进一个节点。当快指针指向尾节点时，停止遍历。

# 求中间节点 只允许遍历一次
def quick_middle(self):
    slow_point = self.head
    fast_point = self.head
    while fast_point.next.next:
        slow_point = slow_point.next
        fast_point = fast_point.next.next
        if not fast_point.next:
            break
    if fast_point.next:
        slow_point = slow_point.next
    return slow_point.data

逆置

新建一个链表，遍历旧链表中的元素。将旧链表中的每一个元素插入到新链表头结点的后面。这样，先插入的数据反而被后插入的数据挤到了后面，原先最前面的数据节点变成了新链表尾节点，而原先的尾节点却变成了新链表最前面的数据节点。风水轮流转，这样就完成了链表的逆置操作。

def reverse(self):
    local_list = SingleLinkedList()
    self.point = self.head
    count = 0
    while self.point.next:
        count += 1
        self.point = self.point.next
        data = self.point.data
        local_list.insert_after_head(data)
    return local_list

打印节点

遍历节点，打印数据。

def print(self):
    # 打印结点
    self.point = self.head
    while self.point.next:
        self.point = self.point.next
        print('{} ->'.format(self.point.data), end=' ')
    print('')

删除尾节点

根据链表大小，找到尾节点，然后类似删除节点的操作。

def delete_by_tail(self, num):
    size = self.get_size()
    assert (num <= size)
    assert (num > 0)
    pos = size - num
    count = 0
    self.point = self.head
    while count < size:
        count += 1
        self.point = self.point.next
        if count == pos:
            pointer = self.point.next
            self.point.next = self.point.next.next
            del pointer

我犯的错误

head 的 next 就指向 node 节点，再让 node 节点指向 head.next，就相当于 node 节点指向了自身，所以循环打印时，永远跳不出循环。

# 典型错法：
# 自身指向自身 打印值时出不去
node = Node(4,None)
head = Node(4,node)
node.next = head.next
i = 0
while node.next:
    i += 1
    print(node.data)
    if i > 12:
        break

这就是本节的全部内容了，看完了要多多用编程巩固一下哦。