1.链表概念

链表是一种动态的数据结构，具体是指一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。链表的数据结构如下图所示。

链表结构

跟数组比较，链表的优势是分配内存空间的灵活性，数组的内存却是一块连续的内存。
根据链表结构不同，链表又可以分为单链表、双向链表和循环链表。

2.单链表基本操作

首先定义节点类用于存储数据和构造链表结构。

class Node:
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

• 判断链表是否为空

    def isEmpty(self):
        return self._head == None

• 获取链表长度
  需要设置计数器和一个循环遍历链表。

    def getlength(self):
        cur = self._head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

• 遍历链表

    def bianli(self):
        cur = self._head
        while cur:
            print(cur.value, '')
            cur = cur.next
        print('\n')

• 头部插入数据
  设置一个新节点指向原节点。

    def add(self, elem):
        cur = Node(elem)
        cur.next = self._head
        self._head = cur

• 尾部插入数据

    def append(self, elem):
        if self._head is None:
            self._head = Node(elem)
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = Node(elem)

• 任意位置插入数据
  注意区分头部尾部和其他位置

    def insert(self, pos, elem):
        if pos <= 0:
            self.add(elem)
        elif pos >= self.getlength():
            self.append(elem)
        else:
            count = 0
            cur = self._head
            while count < pos - 1:
                cur = cur.next
                count += 1
            node = Node(elem)
            node.next = cur.next
            cur.next = node

• 删除数据
  删除数据要注意头部节点和尾部节点的处理，有时候会跳过这两个节点，需要认真考虑。
  1）根据索引删除数据
  此处有一个bug，就是头部删除的时候，明明通过cur将节点指向第二个节点，但实际运行并未起作用，只能改用其他方法。

   def remove1(self, pos):
        if pos < 0 or pos > self.getlength() - 1:
            print('index out of range')
        elif pos == 0:
            self._head = self._head.next
            # cur = cur
            # print(cur.value)
            # print('*'*10)
        else:
            cur = self._head
            count = 0
            while count < pos - 1:
                cur = cur.next
                count += 1
            cur.next = cur.next.next

2）根据元素删除数据
此处有两种思路，第一种思路比较直，是判断next是不是等于要删除元素值，如果是就指向next的next，这个要注意尾部元素没有next，涉及next为None报错的问题，需要特别处理。
第二种思路很巧妙，设置一个前向节点，前向节点记录当前元素之前的值，遇到要删除的元素的时候，直接跳过该节点指向下一个节点。

#思路1：
    def remove_elem(self, elem):
        cur = self._head
        if not cur:
            return None
        if cur.value == elem:
            self._head = cur.next
        while cur.next:
            if cur.next.value == elem:
                cur.next = cur.next.next
            else:
                cur.next = cur.next
            if cur.next is None:
                break
            else:
                cur = cur.next
#思路2：
    def remove(self, elem):
        cur = self._head
        pre = None
        while cur:
            if cur.value == elem:
                if cur == self._head:
                    self._head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

• 查找数据

    def findelem(self, elem):
        cur = self._head
        count = 0
        while cur:
            count += 1
            if cur.value == elem:
                return print('%d is in the %d of chain' % (elem, count - 1))
            cur = cur.next
        return print('%d is not in the chain' % elem)

接下来还有双向链表和循环链表的分析，待补充。