700字范文 > 数据结构（二）----线性表（List）链式存储结构(1)

数据结构（二）----线性表（List）链式存储结构(1)

时间：2021-10-14 20:22:10

线性表List---链式存储结构

相关概念链式存储结构/链式表定义链式存储特点单链表单链表读取单链表插入单链表删除时间复杂度单链表整表创建单链表整表删除顺序存储与链式存储差异Python代码链接Java代码链接

链式存储结构/链式表

定义

数据域：存储数据元素的信息

指针域：存储直接后继位置，指针域中存储的信息叫做指针或链

结点Node：数据域+指针域

所以一般Node类设计：

//javaclass Node{int data; //数据域Node next; // 指针域Node(int val){//构造方法this.data = val;this.next = null;}}

# pythonclass Node(Object){def __init__(self, val):self.data = val;self.next = None;}

n个结点链成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表

头指针：链表中第一个结点的存储位置

头结点：在单链表的第一个结点前附设一个结点（头结点数据域可以不存储任何信息，头

结点的指针域存储指向第⼀个结点的指针）

链式存储特点

⽤⼀组任意的存储单元存储线性表的数据元素，存储单元可以是连续的也可以是不连续的，所以数据元素可以存在内存未被占⽤的任意存储位置

单链表

注：下文中提到的length为链表长度/链表有效元素个数

单链表读取

声明⼀个结点p指向链表第⼀个结点，初始化i从1开始；当i<length时，遍历链表，让p指针向后移动不断指向下⼀结点，i++；若到链表末尾p为空，则说明第i个元素不存在；否则查找成功，返回结点p的数据。

单链表插入

声明⼀个结点p指向链表第⼀个结点，初始化i从1开始；当i<length时遍历链表，p指针向后移动不断指向下⼀个结点，i++当遍历到链表尾p为空，说明第i个元素不存在否则查找成功，⽣成空结点s将要插⼊的结点赋值给s→data单链表的标准插⼊：

s→next=p→next;

p→next=s；

(如果交换语句顺序:p→next=s;s→next=p→next; 会导致，

p→next⾸先会被覆盖成s的地址，那么s→next=s，

此时原本的p→next就没有了上级，链表造成断链)返回成功

单链表删除

声明⼀个结点p指向链表的第⼀个结点位置，初始化i从1开始当i<length时遍历链表，指针p后移，i++当到链表尾部p尾空，说明第i个元素不存在否则查找成功，将要删除的结点赋值为q，即p→next=q删除p→next = q→next（其实4、5步综合来看就是p→next=p→next→next; 只是

我们需要删除的结点data值，多了⼀个变量缓存它）将q结点的data值赋值给e，等待返回释放q结点（一般来说c c++就要手动释放，java和python有自动回收机制）返回e