- 链表
- python实现链表
- 链表的初始化
- 创建
- 元素的插入和删除
- 链表的遍历
- 元素的查询
- 链表的删除
- 链表的逆序
- 判断链表是否有环等
链表
链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。
链表的基本结构
链表是通过一个个节点（Node）组成的，每个节点都包含了称为数据域（value）和指针域（next）的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。
链表的基本元素
- Node(节点)：节点包括两个部分，左边为值域（存放用户数据），右边为指针域（存放指向下一个元素的指针）
- head：指向第一个节点
- tail：指向最后一个节点
- None：链表的最后一个节点的指针域为None值
python实现链表
由于python是动态语言，没有固定类型，可以直接把对象赋值给新的变量，所以在python上一切皆为对象的原理实现链表的操作
- 实现一个简单的单向链表
步骤：- 创建Node（节点）类
- 值域：存放数据
- 指针域：存放指向下一个元素的指针
- 创建一个单链表结构
- 初始化链表
- 检测是否为空链表
- head
- tail
- 创建Node（节点）类
- python实现
- 创建一个节点类并测试
'''
新建单链表Node节点类
'''
'''
新建单链表Node节点类
'''
class Node():
def __init__(self, value=None, next=None):
self.value = value
self.next = next
def get_value(self):
return self.value
def get_next(self):
return self.next
def set_value(self, value):
self.value = value
def set_next(self, next):
self.next = next
head = None
for i in range(1, 6):
head = Node(i,head)
while head != None:
print(head.value) # 输出：5,4,3,2,1,
head = head.next
此时链表结构为：
- 单链表结构
其中包括：
- 初始化链表
- 判断链表是否为空
- 插入节点
链表末尾插入节点
- 判断是否为空链表
- 空链表则头结点指向该节点，length加一
- 非空链表则插入节点到最后一个，length加一
- 链表长度
- 删除节点
- 判断链表是否为空
- 判断删除的是否为头结点
- 判断删除的长度是都合法
- 找到要删除的节点的前一个节点，然后将该节点的下一个指针指向要删除的节点的下一个节点
- 删除节点后length减一
- 修改节点
- 判断链表是否为空
- 判断index是否合法
- 找到待修改节点，修改其value值
- 查找链表
- 判断链表是否为空
- 遍历链表查找节点是否存在
'''
新建一个链表类
'''
class LinkList():
def __init__(self):
# 初始化链表头结点以及链表的长度
self.head = Node()
self.length = 0
def isEmpty(self):
return self.length == 0
def append(self, value):
'''
链表末尾插入节点
* 判断是否为空链表
* 空链表则头结点指向该节点，length加一
* 非空链表则插入节点到最后一个，length加一
'''
node = Node(value)
if self.length == 0:
self.head.next = node
self.length += 1
else:
tempNode = self.head.next
while tempNode.next:
tempNode = tempNode.next
tempNode.next = node
self.length += 1
def len(self):
return self.length
def remove(self, index):
'''
* 判断链表是否为空
* 判断删除的是否为头结点
* 判断删除的长度是否合法
* 找到要删除的节点的前一个节点，然后将该节点的下一个指针指向要删除的节点的下一个节点
* 删除节点后length减一
'''
if self.isEmpty():
print('Error LinkList Length...')
elif (index <= 0 or index > self.length):
print('Error Length...')
elif index == 1:
p = self.head.next
self.head = p
self.length -= 1
else:
p = self.head.next
for i in range(2, index):
p = p.next
q = p.next
p.next = q.next
self.length -= 1
def update(self, index, value):
'''
* 判断链表是否为空
* 判断index是否合法
* 找到待修改节点，修改其value值
'''
if self.isEmpty():
print('This LinkList Is Empty...')
elif (index <= 0 or index > self.length):
print('Error Length...')
else:
p = self.head.next
for i in range(1, index):
p = p.next
p.value = value
def search(self, value):
'''
* 判断链表是否为空
* 遍历链表查找节点是否存在
'''
if self.isEmpty():
print('This LinkList Is Empty...')
else:
p = self.head.next
for i in range(1, self.length + 1):
if p.value == value:
print('Search Success!')
break
elif i == self.length and p.value != value:
print('Search Faild!')
else:
p = p.next
