前言
数据结构中的线性表：分为顺序表和链表。
线性表
线性表（Linear List）是由 n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。
其中：
- 数据元素的个数 n 定义为表的长度 = "list".length() （"list".length() = 0（表里没有一个元素）时称为空表）
- 将非空的线性表（n>=1）记作：（a[0]，a[1]，a[2]，…，a[n-1]）
- 数据元素 a[i]（0≤i≤n-1）只是个抽象符号，其具体含义在不同情况下可以不同
一个数据元素可以由若干个数据项组成。数据元素称为记录，含有大量记录的线性表又称为文件。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。
顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。它具有以下特点：
- 长度固定，必须在分配内存之前确定数组的长度。
- 地址空间连续，即允许元素的随机访问。
- 存储密度大，内存中存储的全部是数据元素。
- 要访问特定元素，可以使用索引访问，时间复杂度为 O(1)。
- 要想在顺序表中插入或删除一个元素，由于要满足地址的连续性，涉及到之后所有元素的移动，因此时间复杂度为 O(n)。
链表
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。
应用
单链表的实现
C 语言实现链表是靠指针与结构体实现的，结构体（结点）的尾部是指向下一结点的指针，Python 没有指针，但是 Python 可以通过定义一个类，类中的一个元素就存放在下一个结点，这样也可以实现链表。
节点对象
#节点对象
class Node():
def __init__(self, val=None):
self.val = val #节点数据值
self.next = None #相连的下一个节点对象
def __str__(self):
return str(self.val)
依靠节点对象，实现单链表的一系列简单操作。
#单链表
class SingleLinkList():
def __init__(self, node=None):
self._header = node
def add(self, var):
'''
单链表添加元素
:param var:传过来的数据
:return:
'''
node = Node(var) # 将数据封装为节点
if self._header == None:
self._header = node
else:
cur = self._header
while cur.next != None:
cur = cur.next #移动游标
cur.next = node
def traversal(self):
'''
遍历输出单链表
:return:
'''
if self._header == None:
return
else:
cur = self._header
while cur != None:
print(cur)
cur = cur.next
def size(self):
'''
链表长度
:return:
'''
count = 0
if self._header != None:
cur = self._header
while cur != None:
count += 1
cur = cur.next
return count
def update(self, index, val):
'''
修改某索引值下的节点数据
:param index:
:param val:
:return:
'''
size = self.size()
node = Node(val)
if size == 0:
print('Empty,can\'t update')
return
if index < 0 or index > size-1:
print('Index is error')
return
cur = self._header
for i in range(index+1):
if index == 0:
self._header = node
self._header.next = cur.next
break
if i == index:
pre.next = node
node.next = cur.next
break
pre = cur
cur = cur.next
def delete(self, index):
'''
根据索引删除链表中的数据（索引从0开始）
:param index: 索引值
:return:
'''
size = self.size()
if size == 0:
print('Empty,can\'t delete')
return
if index < 0 or index > size-1:
print('Index is error')
return
cur = self._header
for i in range(index+1):
if index == 0:
self._header = cur.next
break
if i == index:
pre.next = cur.next
break
pre = cur
cur = cur.next
print(f'pre:{pre},cur:{cur}')
def reverse(self):
'''
单链表反转
:return:
'''
if self._header == None or self.size() == 1:
return self
else:
pre = None # 让头节点.next先断开，因为反转后之前的头结点变为尾节点，所以该节点.next应为置为None
cur = self._header # 从原先的头节点开始
while cur != None:
post = cur.next # 保存下一个节点
cur.next = pre # 更换当前节点的next
pre = cur # 更新pre，用于下个节点的next
cur = post # 按照单链表原先的顺序进行遍历
self._header = pre # 逆转后的头节点
if __name__ == '__main__':
single_link = SingleLinkList()
single_link.add(3)
single_link.add(5)
single_link.add(6)
single_link.add(7)
single_link.add(8)
print("对链表进行遍历")
single_link.traversal()
# print("根据索引对链表进行删除（索引从0开始）")
# index = 4
# single_link.delete(index)
# single_link.traversal()
print("根据索引对链表进行修改（索引从0开始）")
index = 2
single_link.update(index,'a')
single_link.traversal()
print("对链表进行逆向操作之后")
single_link.reverse()
single_link.traversal()
本文作者为hresh，转载请注明。