2022.02.17 《算法通关手册》 链表章数据结构，python版

1 链表基础知识

1.1 定义

物理地址可以连续，也可以不连续，，来存储同类型的数据

优点

存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。

缺点

不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。

链表类型

• 上图为单链表
• 双链表：
  
• 循环链表：
  

1.2 代码实现

创建结点

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

• def _init_(self)在Python里面很常见，类似C++构造函数
• 我们定义这个叫做 LIstNode类 里面,它自己包含了两个参数：① 初始化为0的值 ② 和空的next
• 可以看成，两个参数传进来，传给自己的val,next

创建列表

class LinkedList:
	def __init__(self):
		sefl.head = None

• 有个叫 LinkedList 的结构，Link是连接的意思，List 为列表
• 这个链表只是表头，所以不需要传参数
• 里面有结构 .head，这时候表头也是空的

2 链表的基本操作

2.1 创建一个链表

我们有组数据 data , 以链表方式创建

def create(self, data):
	# 将结点0 作为头结点
	self.head = ListNode(0)
	#这个头结点我们认为叫做cur,但是cur实际指的是链表末端，如果接入新的结点，cur就移动了，不再指向头结点
	cur = self.head
	for i in range(len(data)):
		#我们把data的数据值传到一个新的孤立的结点，名字叫做node
		node = ListNode(data[i]]
		
		#这个新的结点越 链表相连接，cur相当于指在最后的指针
		cur.next = node
		cur = cur.next·	

2.2 求链表长度

def lenth(self):
	count = 0
	#将cur定义在链表的头部位置
	cur = self.head

	while cur:
		count += 1
		cur = cur.next
	
	return count

2.3 查找元素

这时候要传入具体要找的值： value

def find(self, value):
	cur = self.head

	while cur:
		if cur.val == value:
			return cur
		cur = cur.next
	
	return None 

2.4 插入某元素

① 头部插入

这时候要传入具体插入的值： val

def insert(self, val):
	# 构建值为val的结点node
	node = LinkNode(val)
	
	#将这个结点node插入到头
	node.next = self.head
	self.head = node	

② 尾部插入

这时候要传入具体插入的值： val

def insert(self, val):
	node = LinkNode(val)
	cur = self.head
	while cur:
		cur = cur.next
	cur.next = node

③ 中部插入

传入具体插入的值： val;
位置： index

def insert(self, val, index):
	node = LinkNode(val)
	cur = self.head
	
	#记录位置坐标
	count = 0
	
	#count 最终落在需要插入位置的前一位
	while cur and count < index - 1:
		cur = cur.next
		count += 1

	#先判断判断合法性
	if not cur:
		return 'Error'
		
	note.next = cur.next
	cur.next = note

2.5 改变元素

传入具体插入的值： val;
位置： index

# 改变元素
def change(self, index, val):
    count = 0
    cur = self.head
    while cur and count < index:
        count += 1
        cur = cur.next
        
    if not cur:
        return 'Error'
    
    cur.val = val

2.6 删除元素

① 头部删除元素

def removeFront(self):
    if self.head:
        self.head = self.head.next

② 尾部删除

def removeRear(self):
    if not self.head.next:
        return 'Error'

    cur = self.head
    while cur.next.next:
        cur = cur.next
    cur.next = None

③ 中部删除

传入具体删除位置： index;

def removeInside(self, index):
    count = 0
    cur = self.head
    
  	#找到index这个位置前一个位置cur
    while cur.next and count < index - 1:
        count += 1
        cur = cur.next
        
    if not cur:
        return 'Error'
        
    #删除操作，要删的结点为del_node
    del_node = cur.next
    cur.next = del_node.next