什么是链表

链表是一种在物理上非连续、非顺序的数据结构，由若干节点组成

单向链表
单向链表的每一个节点包含两部分，一部分是存放数据的data ，另一部分是指向下个节点的next指针
链表的第一个节点叫做头节点，最后一个节点称为尾节点，尾节点的next指针指向空

多向链表
多向链表的每一个节点包含三个部分，分别拥有data和next指针，还有指向前置节点的prev指针
头节点的prev指针指向空，尾节点的next指针指向空

链表的存储特点链表的存储是随机存储，依靠next指针关联

链表的基本操作

链表的查找
链表的查找只能按顺序进行访问，从头节点开始，依靠next指针逐一查找，所以链表的查找的时间复杂度最差是O(n)

链表的插入
原理:
1.把新节点的next指针指向原被插入位置next指针所指向的节点
2.插入位置节点的next指针，指向新节点
如果是尾部插入则把最后节点的next指针指向新插入的节点
如果是头部插入，则把新节点的next指针指向原先头节点，新节点变成链表的头节点
链表中间插入实现

  1. class Node:
  2.     """定义链表节点"""
  3.     def __init__(self, data):
  4.         self.data = data
  5.         self.next = None
  8. class LinkList:
  9.     """默认链表为空"""
  10.     def __init__(self):
  11.         self.size = 0
  12.         self.head = None
  13.         self.last = None
  15.     def get_1(self, index):
  16.         if index < 0 or index >= self.size:
  17.             raise Exception("超过链表节点范围！")
  18.         p = self.head
  19.         for i in range(index):
  20.             p = p.next
  21.         return p
  23.     def insert1(self, data, index):
  24.         if index < 0 or index > self.size:
  25.             raise Exception("超过链表节点范围！")
  26.         # 创建新节点
  27.         node = Node(data)
  28.         if self.size == 0:
  29.             # 空链表
  30.             self.head = node
  31.             self.last = node
  32.         elif index == 0:
  33.             # 插入头部
  34.             # 新节点的next指针指向原先头节点
  35.             node.next = self.head
  36.             # 新节点变成头节点
  37.             self.head = node
  38.         elif index == self.size:
  39.             # 插入尾部
  40.             # 原先头节点next指针指向新节点
  41.             self.last.next = node
  42.             # 新节点变成尾指针
  43.             self.last = node
  45.         else:
  46.             # 插入中间
  47.             prev_node = self.get_1(index-1)
  48.             # 新节点的next指针指向插入位置的节点
  49.             node.next = prev_node.next
  50.             # 插入位置前节点next指针指向插入节点
  51.             prev_node.next = node
  52.         self.size += 1
  54.     def output(self):
  55.         p = self.head
  56.         while p is not None:
  57.             print(p.data)
  58.             p = p.next
  61. if __name__ == '__main__':
  62.     linkesList = LinkList()
  63.     linkesList.insert1(3, 0)
  64.     linkesList.insert1(4, 0)
  65.     linkesList.insert1(9, 1)
  66.     linkesList.insert1(5, 1)
  67.     linkesList.output()

链表的删除
原理：
1.把删除节点的前置节点的next指针，指向删除元素的下一个节点
2.如果是头节点删除，把链表的头节点设为原先头节点next指针所指的节点即可
3.如果是尾节点删除，把倒数第二个节点的next指针指向空即可
链表删除的实现原理

class Node:
    """定义链表节点"""
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkList:
    def __init__(self):
        self.size = 0
        self.head = None
        self.last = None

    def get_1(self, index):
        if index < 0 or index >= self.size:
            raise Exception("超过链表节点范围！")
        p = self.head
        for i in range(index):
            p = p.next
        return p

    def insert1(self, data, index):
        if index < 0 or index > self.size:
            raise Exception("超过链表节点范围！")
        # 创建新节点
        node = Node(data)
        if self.size == 0:
            # 空链表
            self.head = node
            self.last = node
        elif index == 0:
            # 插入头部
            # 新节点的next指针指向原先头节点
            node.next = self.head
            # 新节点变成头节点
            self.head = node
        elif index == self.size:
            # 插入尾部
            # 原先头节点next指针指向新节点
            self.last.next = node
            # 新节点变成尾指针
            self.last = node

        else:
            # 插入中间
            prev_node = self.get_1(index-1)
            # 新节点的next指针指向插入位置的节点
            node.next = prev_node.next
            # 插入位置前节点next指针指向插入节点
            prev_node.next = node
        self.size += 1

    def remove_1(self, index):
        if index < 0 or index >= self.size:
            raise Exception("删除超过链表范围！")
        if index == 0:
            # 删除头节点
            removed_node = self.head
            # 把头节点设为原先头节点的next指针指向的节点
            self.head = self.head.next
        elif index == self.size - 1:
            # 删除尾节点
            prev_node = self.get_1(index-1)
            removed_node = prev_node.next
            # 倒数第二个节点的next指针指向空
            prev_node.next = None
            self.last = prev_node
        else:
            # 删除中间节点
            prev_node = self.get_1(index-1)
            # 原删除节点next指针指向的节点
            next_node = prev_node.next.next
            # 原删除节点
            removed_node = prev_node.next
            # 把 指向原删除节点的前置节点的next指针指向删除节点的下一个节点
            prev_node.next = next_node
        self.size -= 1
        return removed_node

    def output(self):
        p = self.head
        while p is not None:
            print(p.data)
            p = p.next


if __name__ == '__main__':
    linkesList = LinkList()
    linkesList.insert1(3, 0)
    linkesList.insert1(4, 0)
    linkesList.insert1(9, 1)
    linkesList.insert1(5, 2)
    linkesList.remove_1(1)
    linkesList.output()


链表的优势和劣势

优势链表适合写操作多的场景, 时间复杂度为O(1)
劣势不适合读操作多的场景, 时间复杂度为O(n)