兜兜绕绕两三天终于到了重要的地方了，当初想到要学数据结构的时候，以及后面了解到数据结构的语言无关性之后，心里不免还是有个疑问：Python也没有指针啊，怎么样像C语言那样通过指针来实现更高级的数据结构呢？众所周知，C语言实现的链表是由一个一个的结点构成，每个结点分为数据域和指针域，指针域中存储了其后继结点的地址，通过地址来访问下一个结点，然后一步一步的串联起来形成了一个单链表。但是Python没有指针啊，难不成有什么更高级的玩意儿来替代指针这个东西？带着这个大大的问号，我开始了链表的学习。

class Node(object):
    """节点"""
    def __init__(self, elem):
        self.elem = elem
        self.next = None

当老师直接拿出这个的时候
我：

我简直就是黑人问号，居然可以这么玩！不过仔细想想，好像也有点道理，毕竟Python中万物皆对象嘛，一个结点用类的方式来实现也比较符合Python的语法结构，一如既往的那么简洁优雅，哈哈！其实这个类的方法实现链表类似于C语言中的结构体实现链表不过其对于指向下一个结点的方式略有不同。
elem是数据域，next类似于C语言中的指针域，是下一个结点的标识。所以一个单一结点类对象的next指向None。
在这里我要特别强调一下Python中的“=”的特殊含义以及作用。Python中的“=”是一种指向性的表示，self.next = None即节点的next指向为None，相当于我在None上贴了一个标签，标签的名字是next，这个next指向None。

链表有以下操作方法，包括最基本的增删改查和其他的一些方法。

• is_empty() 链表是否为空
• travel() 遍历整个链表
• length() 链表长度
• add(item) 链表头部添加元素
• append(item) 链表尾部添加元素
• insert(pos, item) 指定位置添加元素
• search(item) 查找节点是否存在
• remove(item) 删除节点

一个单链表首先要有一个头结点：

class SingleLinkList(object):
    """单链表"""
    def __init__(self, node=None):
        self.__head = node

这个函数主要返回就是True和False，如果头结点是空，那么这个链表就是一个空链表.

    def is_empty(self):
        """判断链表是否为空"""
        return self.__head == None

cur是一个游标，也就是一个标签，开始指向头结点，随着遍历循环的开始，只要这个结点没有指向None，cur = cur.next游标向下一个结点移动。

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

链表长度的计算方式就是遍历法，遍历一个结点，只要这个结点不是None，那么计数器+1。

    def length(self):
        """链表长度"""
        # cur游标，用来移动遍历节点
        cur = self.__head
        # count记录数量
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

向链表头部添加元素很简单，因为链表是一个活动性很大的数据结构，其中的每一个结点彼此只靠next相连接，其物理存储之间没啥太大的关系，在头部添加元素我们只需要将这个结点放在原先的第一个结点之前，然后再让头结点指向这个新添加的结点就可以了。然后我们就要考虑一下链表是空的情况了，此时self.__head = None然后再将头结点加上去，代码任然没问题。

    def add(self, item):
        """链表头部添加元素，头插法"""
        node = Node(item)
        node.next = self.__head
        self.__head = node

在链表的尾部添加元素也比较简单首先假设链表非空，单链表只能由头结点往后遍历找到最后一个结点，其指向为None，也就是cur.next = None，然后将cur.next指向要添加的这个结点。如果是空链表，直接将头结点指向要添加的这个节点就可以。

    def append(self, item):
        """链表尾部添加元素, 尾插法"""
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

pos是要添加的位置，即第几个结点。先假设链表非空，并且是从中间插入结点。先建立一个指向头结点的cur游标，然后循环遍历，并让计数器count每遍历一次次数加一，直到count=pos-1，这里为什么是pos-1而不是pos的原因是如果插入到3这个位置，其实cur游标是停在2这里，然后结点的next指向pos这个结点，cur的next则指向添加的这个结点，听起来有点绕啊，大概过程就在下面这个图里，这个地方需要停下来好好想一想的。然后在考虑特殊情况，如果pos<=0得话，默认就是空节点，直接调用add函数即可，如果pos大于链表的长度，就是在尾部添加结点，调用apped函数。

    def insert(self, pos, item):
        """指定位置添加元素
        :param  pos 从0开始
        """
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
           cur = self.__head
            count = 0
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 当循环退出后，pre指向pos-1位置
            node = Node(item)
            node.next =cur.next
           cur.next = node

遍历查找即可。

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

先假设删除的结点是中间的部分，前后均有结点与其相连。为了便于理解，这里我们整了两个游标pre和cur，其中pre指向None，cur指向头结点，然后执行pre = cur，cur = cur.next就能够一步步的将两个游标向前移动，并且始终各自指向相连的两个结点。当cur指向要删除的结点时，执行pre.next = cur.next，这里是什么意思呢？cur的next是要删除节点的下一个结点，怎样才算删除呢？当我们这个结点与真个链表没有关系的时候就算是删除了，pre的next如果跳过我们删除的结点，直接指向其下一个结点，不就是把这个结点抛弃了，使其与链表没有关系，然后删除了嘛！如果这个结点是第一个头结点，删除他的话就比较简单了，直接把头结点__head指向要删除节点的下一个结点不就OK了嘛。

 def remove(self, item):
        """删除节点"""
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                # 先判断此结点是否是头节点
                # 头节点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

测试代码

if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())
    ll.append(1)
    print(ll.is_empty())
    print(ll.length())
    ll.append(2)
    ll.add(8)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)
    ll.insert(-1, 9)
    ll.travel()
    ll.insert(3, 100) 
    ll.travel()
    ll.insert(10, 200) 
    ll.travel()
    ll.remove(100)
    ll.travel()
    ll.remove(9)
    ll.travel()
    ll.remove(200)
    ll.travel()

写到这里，顺便给大家推荐我的资源很全的Python全栈QQ群 711977825 这里有资深程序员分享以前学习心得，学习笔记，还有一线企业的工作经验，且给大家精心整理一份python零基础到项目实战的资料，每天给大家讲解python最新的技术，前景，学习需要留言的小细节等。

图片以及某些代码来源于我学习的资料！今天我们就只讲了单链表的具体操作，后面会慢慢的介绍其他的高级数据结构类型（要给我点时间整明白再讲），既然我们知道了Python中如何实现“指针”以及结点这个玩意儿怎么定义，那么其他的数据结构应该就不在话下了！

更：看到很多大佬的评论了，我这写的真是链表，列表那篇我也写了有兴趣可以看看，链表和列表还是有区别的，我不是说列表放着不用在这里写链表没事做，我是有Python来实现数据结构，我是在记录和分享自己的学习历程，不是技术博客，毕竟CSDN还是有很多刚来的人来这学习的，希望和大家一起进步。
新手上路，技术有限，不喜勿喷