一、链表

1.1目的

解决顺序表存储数据有上限，并且插入和删除操作效率低的问题

1.2概念

链表：链式存储的线性表，使用随机物理内存存储逻辑上连续的数据

链表的组成：由一个个结点组成

结点：由数据域和链接域组成，是链表的基本单位

数据域：存储数据元素的区域

链接域：记录下一个结点所在位置的区域

头结点：虚设的一个结点，连接域专门记录链表第一个结点的位置，数据域专门记录链表的长度

1.3链表的种类

单向链表、双向链表、循环链表

二、单向链表

2.1单向链表的概念

只能通过头结点或链表的头，单向的访问后继结点的链表叫单向链表

2.2结点和链表类的格式

1】包含存储数据元素的数据域

2】有一个存储下一个结点的位置域

#封装普通节点的类
class Node:
    #构造函数，定义结点的属性
    def __init__(self,data):
        self.data=data#普通结点的数据域
        self.next=None#普通结点的连接域，刚构造的结点该位置域为空
#封装链表的类（封装头节点）
class Link_list():
    def __init__(self,node=None):
        self.size=0#头结点的数据域为0 链表的长度为0
        self.head=node#头结点的连接域指向None

2.3单向列表的相关操作（成员函数的封装）

1】单向链表的创建

2】判空

#判空
    def is_empty(self):
        return self.head
    #   return self.size==0  或者判断长度是否为零

3】头插

函数功能：将一个结点以头插的方式插入到头结点的后面

思路：

参数：self链表，要插入的数据

注意事项：需要申请结点封装数据

                  插入成功链表长度自增

#头插
    def add_head(self,value):
        #创建一个新的结点
        node=Node(value)
        node.next=self.head
        self.head=node
        self.size+=1

4】尾插

函数功能：将新的节点增加到链表的尾部。思路：（如上图）

函数返回值：无

函数名：符合命名规则

参数列表：self 链表，要插入的数据

注意事项：插入成功，链表自增

#尾插
    def add_tail(self, value):
        #创建一个结点node
        node = Node(value)
        #找最后一个结点
        # q = self.head
        # i=1
        # while i<self.size:
        #     q=q.next
        #     i+=1
        # q.next=node
        # self.size+=1
        #第二种方法
        q = self.head
        while q.next:
            q = q.next
        q.next = node
        self.size += 1
        #第三种
        # while True:
        #     q=q.next
        #     if not q.next:
        #         q.next = node
        #         self.size+=1
        #         break

5】任意位置插

函数功能：在指定的位置插入一个节点 思路：如上图

函数返回值：无

函数名：符合命名规则

参数列表：self链表、要插入的位置、要插入的数据

注意事项：1、判断要插入的位置是否合理

2、成功插入 ；链表长度自增

3、如果是第一个位置，做头插

#任意位置插
    def add_any(self, id, value):
        node = Node(value)
        if id == 1:
            self.add_head(value)
        elif id == self.size+1:
            self.add_tail(value)
        elif id>self.size+1:
            print('插入失败')
            return
        else:
            q = self.head
            i = 1
            while i < id - 1:
                q = q.next
                i += 1
            node.next = q.next
            q.next = node
            self.size += 1

6】头删

#头删
    def del_head(self):
        self.head = self.head.next
        self.size -= 1

7】尾删

#尾删
    def del_tail(self):
        if self.size==1:
            self.head=None
        else:
            q = self.head
            for i in range(self.size - 2):
                q = q.next
            q.next = None
            self.size -= 1

8】任意位置删

#任意位置删
    def del_any(self,id):
        if id==1:
            self.del_head()
        else:
            q = self.head
            for i in range(id - 2):
                q = q.next
            q.next = q.next.next
            self.size -= 1

9】遍历

函数功能：从头到尾打印出链表中每个节点的数据域的数据

函数返回值：无

函数名：符合命名规则

参数列表：self 链表

注意事项：判空

#遍历
    def show(self):
        #判空
        if self.is_empty():
            print('遍历失败')
            return
        else:
            q = self.head
            while q :
                print(q.data,end=' ')
                q = q.next
            print()