一、为什么要学习数据结构

python 语言和标准库自带了很多数据结构，比如 list、set、dict、tuple、queue、heapq等，所以很在标准库或者第三方库提供的数据结构够用的情况下，不需要自己再写数据结构。

当然，掌握了数据结构的原理之后，面对大量数据的时候，可以更轻松地选择合适的数据结构，以及在标准数据结构不够用的情况下，可以定制化实现自己的数据结构。

为什么要有数据结构呢？ 可以考虑在不使用数据结构的情况下，如果需要处理100个数据，是不是就需要使用100个变量来表示它们，如果是10000个数据呢，直接就没法玩儿了。

所以，数据结构就是把大批量要处理的数据组织起来，方便编程的时候使用。数据组织的方式（结构）不同，就形成了多种多样的数据结构。每种结构都有各自的特点以及适用场景。比如，链表只能顺序存取一个数据，二叉搜索树可以 O(log(n))的时间复杂度存取数据，哈希表 可以使用 O(log(1))的复杂度存取数据但是比较适用于 key->value的数据类型。

二、链表是一种什么样的数据结构

接下来就讲一下 链表（List）这个数据结构的原理。
List是一种比较简单的数据结构，把数据通过指针(引用)串起来，组成一个链，操作者只需要拿着 head 或者 tail（双向链表） 就可以操作所有数据了。

ListNode1 --> ListNode2 --> ListNode3 --> ListNode4

每个 ListNode 包含 数据 以及对下一个 ListNode 的引用，如果我们要在某个位置上插入一个节点，比如在 ListNode3后面插入 ListNode5， 插入之后的情况就是：
ListNode1 --> ListNode2 --> ListNode3 --> ListNode5 --> ListNode4

三、python 语言实现简单的 List 结构

我们使用 python 一步步来实现一下这个数据结构，主要实现 find、insertBefore、insertAfter、remove、append、count 这几种操作。
这里主要是学习之用，所以这里的操作和一些标准库的 List 提供的操作接口不太一样。对于高级语言标准容器的List， 一般不会暴露内部的 ListNode。
关于List 的可迭代性，以及更标准的操作封装，放在下一次实现吧。
下面就是代码了，如果有些不对的地方，欢迎大家指正。

#  -*- coding: utf-8 -*-class ListNode():
    """
    定义链表节点的class，表示链表中的一个节点，其中存储了数据以及下一个节点的指针
    """  
    def __init__(self,value):
        self.value = value
        self.next = Noneclass List():
    """
    定义链表类，初始化函数中定义了 head、tail 和 count 变量 
    head 是头结点，并不用来保存数据，所以，真正数据从 head.next开始
    这样做的好处，在链表头部插入节点或者最后一个节点被删除之后，
    链表的 head 应用不需要变化，简化的代码的编写。
    """
    def __init__(self):
        self.head = ListNode(0)
        self.tail = self.head
        self.count = 0

    def __len__(self):
        """
        返回链表的长度，len( listA) 函数会调用链表对象  __len__()函数     
        """
        return self.count    def append(self, value):
        """
        在链表的结尾添加一个节点，节点的数据为 value
        因为 List 类保存链表的末尾节点，因此直接加入到tail 的后面
        """
        self.tail.next = ListNode(value)
        self.tail = self.tail.next
        self.count+=1
        return self.tail    def find(self, value):
        """
        查找第一个值为 value的几点，并返回ListNode
        """
        cur = self.head.next        while cur and cur.value != value:
            cur = cur.next        return cur    def remove(self, node):
        """
        将某个 ListNode 从链表中删除，需要找到这个节点的
        上一个节点，然后将上一个几点的 next 指向被删除节点的下一个节点。
        """
        pre = self.head        while pre and pre.next != node:
            pre = pre.next        if pre:
            pre.next = node.next            if node == self.tail:
                self.tail = pre
            self.count -= 1

            return node        else:            return None

    def insertBefore(self, node, value):
        """
        在指定节点 node 之前插入值为 value 的新节点，
        需要找到 node 节点的前一个节点，然后 node 和前一个节点之间插入新节点。
        这里需要处理 node 为 None 的时候，插入到链表的最后位置。
        """
        if node is None:            return self.append(value)

        pre = self.head        while pre and pre.next != node:
            pre = pre.next        
        if pre:
            newNode = ListNode(value)
            pre.next,newNode.next = newNode,node
            self.count+=1
            return newNode        else:            return None

    def insertAfter(self, node, value):
        """
        在指定节点 node 之后插入值为 value 的新节点，
        这里需要处理 node 为 None 的时候，插入到链表的最前位置。
        """
        if node is self.tail:            return self.append(value)

        newNode = ListNode(value)
        newNode.next = self.head.next
        self.count +=1
        if node is None:
            self.head.next = newNode            if self.tail is self.head:
                self.tail = newNode        else:
            node.next,newNode.next = newNode, node.next            if self.tail is node:
                self.tail = newNode        return newNode    def count(self):
        return self.countif __name__ == '__main__':    # append
    l = List()
    l.append(1)
    l.append(2)
    l.append(3)    # find
    v1 = l.find(1)
    v2 = l.find(2)
    v3 = l.find(3)
    print(v1.value)
    print(v1.value)    #remove
    l.remove(v1)
    l.remove(v2)    #insert before 
    v22 = l.insertBefore(v3, -2)
    v33 = l.insertBefore(v22, -3)    #insert after
    v4 = l.insertAfter(v3, 4)
    v5 = l.insertAfter(v4, 5)    #count 5
    print(len(l))    #遍历输出链表的各个节点，链表的遍历，冲 head.next 开始
    #print list -3, -2, 3, 4, 5
    cur = l.head.next    while cur:        #这里用来判断是否是最后一个节点，最后一个节点输出的时候不需要添加逗号
        if cur.next:            print "%d,"%(cur.value),        else:            print cur.value
        cur = cur.next

作者：lovecoding_193b
链接：https://www.jianshu.com/p/73dd103614ab