数据结构之链表

Author：baiyucraft

BLog： baiyucraft’s Home

  本篇文章记录链表的一些常见使用（不断更新中）

一、链表简介

  链表是一种物理储存单元上非连续、非顺序的储存结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

二、常见链表种类及其基本操作

1.单链表

  最常见的链表，在LeetCode中，结点被表示为：

1
2
3
4
5
6
class ListNode:
	def __init__(self, val=0, next=None):
		# 数据域 
		self.val = val
		# 指针域，指向下一个结点
		self.next = next

  1）尾插法建表

1
2
3
4
5
6
7
8
def tail_insert_LinkList(self, vals: List) -> ListNode:
	# 头结点
	ehead = ListNode(0)
	p = ehead
	for val in vals:
		p.next = ListNode(val)
		p = p.next
	return ehead.next

  2）尾插法建表

1
2
3
4
5
6
7
def head_insert_LinkList(self, vals: List) -> ListNode:
	# 头结点
	ehead = ListNode(0)
	for val in vals:
		new_node = ListNode(val, ehead.next)
		ehead.next = new_node
	return ehead.next

  3）输出链表

1
2
3
4
5
6
7
def print_LinkList(self, head: ListNode) -> None:
	p = head
	res = []
	while p:
		res.append(p.val)
		p = p.next
	print(res)
DataStructure
#Python #LeetCode #数据结构 #链表
数据结构之链表
http://baiyucraft.top/DataStructure/DataStructure-List.html
作者
baiyucraft
发布于
2021年5月20日
许可协议