线性表的链式存储结构以及单链表的插入和删除原理实现

线性表的链式存储结构

线性表中的每个元素最多只有一个前驱元素和一个后继元素（其逻辑结构），因此可以采用链式存储结构存储。

链表

线性表的链式存储结构称为链表。在链表中每个结点不仅包含有元素本身的信息（称之为数据成员），而且包含有元素之间的逻辑关系的信息，即一个结点中包含有后继结点的地址信息或前驱结点的地址信息，我们把它称作指针成员。这样能够方便找到后继或前驱结点。

• 注:java语言中不存在指针的概念，我们描述只是为了方便，这里指针成员实际上是存放前驱或者后继结点的引用且链表不具有随机访问任一元素的特点。
• 如果每个结点只设置一个指向其后继结点的指针成员，这样的的链表我们称之为线性单向链表，简称单链表
• 如果每个结点中设置两个指针成员，分别指向于其前驱结点和后继结点，这样的链表成为线性双向链表，简称双链表。无前驱或后继结点的相应指针使用null表示。

为了便于在链表中的插入和删除结点，通常链表带有一个头结点，并通过头结点指针唯一标识该链表，因为从头指针所指的头结点出发，沿着结点的链可以访问到链表中的每个结点。如图：

通常将p指向的结点成为p结点或者结点p；头结点为head的链表称为head链表，头结点中不存放任何数据元素（空表是只包含头结点的链表），存放序号为0的元素的结点成为开始结点，存放终端元素的结点称为终端节点或尾节点，链长一般不计头结点。

单链表

LinkNode< E >泛型类的定义

• 代码示例：

class LinkNode<E>    //单链表结点泛型类
{
 E data;
 LinkNode<E>next;
 public LinkNode();  //构造方法
 {
     next=null;
 }
 public LinkNode(E d) //重载构造方法
 {
     data=d;
     next=null;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入和删除操作

插入和删除是单链表中最常用的操作，它是建立单链表和相关基本运算算法的基础。

1. 插入结点操作：插入运算是将结点s插入单链表中p结点的后面。为了插入结点s需要修改结点p中的指针成员，令其指向结点s，而结点s的指针成员应指向p结点的后继结点。关键代码如下：

    s.next=p.next;
    p.next=s;
1
2

• 注：代码顺序不能颠倒

• 图解：

2. 删除结点操作：删除运算时删除单链表中p结点的后继结点，其操作是将p结点的next运算修改为其后继结点的后继结点。代码描述如下

p.next=p.next.next;
1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Nu9QfR5X-1667407574800)(https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/ddc187e6f4c045d8b7d70d971dddb99e~tplv-k3u1fbpfcp-watermark.image?)]

头插法建立单链表

该方法从一个空表开始，依次读取数组a中的元素，生成新结点s，将读取的数据存放到新结点的数据成员中，然后将新结点s插入当前列表的表头上。一直重复这个过程，直到所有元素读完为止。

• 代码示例：

public void CreateListF(E[] a){
    LinkNode< E > s;
for (int i = 0; i < a.length; i++) {    //循环建立数据结点s
    s=new LinkNode<E> (a[i]);            //新建存放a[i]元素的结点
    s.next=head.next;                    //将s结点插入开始结点之前，头结点之后
    head.next=s;
}
    
}
1
2
3
4
5
6
7
8
9