700字范文 > 链表的基本概念以及java实现单链表-循环链表-双向链表

链表的基本概念以及java实现单链表-循环链表-双向链表

时间：2021-03-19 09:26:41

前言

线性结构是非常简单且常用的数据结构，而线性表则是一种非常典型的线性结构。

线性表定义线性表的数据结构链表

单链表

单链表的定义单链表的插入和删除单链表的遍历，清空，判空，获取指定结点循环链表

循环链表的定义循环链表的插入和删除循环链表的遍历，清空双向链表

双向链表的定义双向链表的插入和删除

本节代码传送门，欢迎star：/mcrwayfun/java-data-structure

1. 线性表的定义

通常将线性表定义为n个元素的有限的序列，可以表为为

其中L为表名，a是表中不可再分割的原子数据，亦称为结点或者表项。n是表中表项的个数，也被称为表的长度。当n=0时叫做空表。

线性表的的第一个表项称为表头，最后一个项称为表尾。因为线性表是有序的，这就意味着每个相邻的表项之间都有直接前驱和直接后继的关系，也就是说，除了表头没有直接前驱，其他表项有且仅有一个直接前驱；除了表尾没有直接后继，其他表项有且仅有一个直接后继。

2. 线性表的数据结构

在类库中，java语言包含了一些普通数据结构的实现。该语言的这一部分通常叫做Collections API，表ADT是在Collections API中实现的数据结构之一，看一下其基本的方法：

public interface Collection<AnyType> extends Iterable<AnyType>{// 返回表中元素个数int size();// 判断表是否为空boolean isEmpty();// 清空一张表的数据void clear();// 判断表是否含有数据项xboolean contains(AnyType x);// 向表中添加一个新的元素xboolean add(AnyType x);// 移除表中的元素xboolean remove(AnyType x);}

3. 链表

链表可以分为有序线性表和无序线性表，本小节仅考虑无序线性表，即链表。链表又分为单链表，环形链表和双向链表。下面将围绕接口Collection中的基本方法实现链表以及完成一些拓展。

3.1 单链表

为了克服顺序表的缺点（新增或删除元素开销大；需要事先分配连续的存储空间），采用链接方式来存储线性表，通常将链接方式存储的线性表成为链表。链表适用于插入或者删除频繁，存储空间需求不定的情形。

3.1.1 单链表的定义

单链表的存储结点包含两部分，一个是数据域（data），用于存储线性表的一个数据元素；一个是指针域（link），用于存放一个指针，该指针指向链表中下一个结点的开始存储地址。用图表示为：

用API可以表示为，其中item为数据域，next为指针域：

class Node<E> {E item;Node<E> next;}

一个线性表的单链表结构可以用下图表示：

其中，单链表的表头可以通过头指针first找到，其他结点的地址则在前驱结点的link域中，表尾结点没有后继，其link域中存放了一个空指针NULL作为终结。因此，要访问单链表中的任一结点，都需要根据头指针first找到第一个结点，再按照各结点link域中存放的指针顺序往下寻找。因此，操作单链表最重要的便是维护一个头指针first

3.1.2 单链表插入和删除

利用单链表来表示线性表，使得插入和删除操作变得非常方便，只需要改变链表结点中的指针值，无需移动表中的元素，就能高效的完成插入和删除操作。现有单链表

首先来看下单链表的ADT，MyList是一个接口，定义了线性表的基本接口，会放在源码中，这里不作展示

public class SinglyLinkedList<E> implements MyList<E> {// 表中元素个数int size = 0;// 表头指针Node<E> first;// 存储结点private static class Node<E> {E item;Node<E> next;public Node(E item, Node<E> next) {this.item = item;this.next = next;}}}

插入操作

对于插入算法，需要在数据项ai结点后插入一个新的元素x，那么可能会出现3种情况：

（1）在表的表头插入一个新结点，那么新结点成为表头，并将first指针指向新结点

// 新结点链向原表头newNode.next = first;// 新结点成为表头first = newNode;

（2）若ai是链表的最后一个结点，则新结点应追加在表尾。那么新元素成为表尾，且指针域为NULL。定义检测指针cur，需要遍历链表，找到原来的表尾an，新结点则在表尾后插入

// 循环找到表尾last，last指针域指向新结点cur.next = newNode;

（3）若ai即不是表头，也不是表尾。此时，首先让一个检测指针cur指向ai所在的结点，新结点插入到ai所在结点后

// 新结点指针域指向ai的下一个结点newNode.next = cur.next;// ai指向新结点cur.next = newNode;

由上述例子可以得知，在链表中间插入和末尾插入的算法相同，所以可以合并：

综合上述算法，最终可以得到单链表的插入算法：

/*** 为链表添加一个元素** @param index 指定位置* @param e数据*/@Overridepublic void add(int index, E e) {// 检查index是否越界或数据e是否为空if (checkPositionIndex(index) || assertDataNull(e)) {return;}Node<E> newNode = new Node<>(e, null);// 在头结点插入if (index == 0) {newNode.next = first;first = newNode;} else {// 在中间和末尾结点插入// 获取index的前一个数据Node<E> node = node(index - 1);newNode.next = node.next;node.next = newNode;}size++;}

拓展，直接向表的末尾添加新结点：

/*** 在链表尾添加一个元素** @param e*/@Overridepublic void add(E e) {// 检查数据e是否为空if (assertDataNull(e)) {return;}Node<E> newNode = new Node<>(e, null);// 获取当前末尾结点// 如果头结点不存在则创建if (isEmpty()) {first = newNode;} else {// 获取到需要添加的头一个Node<E> node = node(size - 1);node.next = newNode;}size++;}

删除操作

对于删除算法，需要删除指定位置的数据项，那么可能会出现2种情况：

（1）在链表的第一个结点处删除，即删除链表的第一个结点，那么我们只要将first指针指向下一个结点即可

first = first.next;

（2）删除链表中间和尾部的结点。假设删除表中第i个结点，让i-1结点的link域保存i+1个结点的地址

// 遍历找到i-1结点，让i-1结点的link域保存i+1个结点的地址node.next = node.next.next;

综合上述算法，最终可以得到单链表的删除算法：

/*** 移除一个指定元素** @param index*/@Overridepublic void remove(int index) {// 检查index是否越界if (checkPositionIndex(index)) {return;}// 移除头元素if (index == 0) {first = first.next;} else {// 移除中间或者尾部元素// 获取index的前一个数据Node<E> delNode = node(index - 1);delNode.next = delNode.next.next;}size--;}

3.1.3 单链表的遍历，清空，判空，获取指定结点

遍历操作

/*** 打印链表*/@Overridepublic void print() {Node<E> cur = first;while (cur != null) {System.out.print(cur.item + " ");cur = cur.next;}System.out.println();}

清空链表操作

遍历链表，清空每个结点的数据项和指针域。头指针first = NULL和size = 0

/*** 清空链表*/@Overridepublic void clear() {for (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x = next;}first = null;size = 0;}

判空操作

/*** 判断链表是否为空** @return*/@Overridepublic boolean isEmpty() {return first == null;}

获取指定结点

/*** 获取指定位置的Node** @param index* @return*/Node<E> node(int index) {Node<E> x = first;for (int i = 0; i < index; i++) {x = x.next;}return x;}

3.2 循环链表

在单链表中，如果已知某个结点的地址，想知道该结点的下一个结点地址，那么是非常方便的，所需的时间开销为O（1）。但是想要知道该结点的前驱，就必须从表的最前端开始逐个考查，看谁的后继是指定结点，谁就是该结点的直接前驱，所需时间开销为O（n）；另外，在单链表中，已经某个结点，想要寻找其他所有结点，在大多数情况下是不可能的。

为了解决以上这两个问题，出现了单链表的变形，双向链表和循环链表。

3.2.1 循环链表的定义

循环链表本质也是线性表，它的结点结构与单链表的相同。与单链表不同的是，循环链表的表尾结点link域存储不是NULL，而是存储了指向表头指针first的地址。这样，只要知道了表中一个结点的地址，就能遍历表中任何其他的结点。

3.2.2 循环链表的插入和删除

首先来看一下循环链表的ADT，与单链表不同的是，循环链表不仅要维护first，也要维护一个last指针。

public class CircularLinkedList<E> implements MyList<E> {// 表中元素个数int size = 0;// 表头指针Node<E> first;// 尾指针Node<E> last;// 存储结点private static class Node<E> {E item;Node<E> next;public Node(E item, Node<E> next) {this.item = item;this.next = next;}}}

插入操作

对于插入算法，需要在数据项ai结点后插入一个新的元素x，那么可能会出现3种情况：

（1）需要在表头插入新结点。新结点的link域指向原来的头指针；新结点成为新的头指针；尾指针指向新结点

// 新结点link域指向原来的头指针newNode.next = first;// 新结点成为新的头指针first = newNode;// 尾指针指向新结点last = newNode;

(2) 在表的末尾插入新结点，新结点的link域指向头指针first；原来的last指针link域指向新结点；尾指针last指向新结点

// 新结点link域指向头指针firstnewNode.next = first;// last指针link域指向新结点last.next = newNode;// 尾指针last指向新结点last = newNode;

(3) 在表的中间部分插入新结点。找到插入结点的前一个结点；新结点的link域指向前结点的link域；前结点link域指向新结点；

// 找到插入结点的前结点，假设为node// 新结点的link域指向前结点的link域newNode.next = node.next;// 前结点link域指向新结点node.next = newNode;

综上，循环链表的插入算法可以总结为：

/*** 在链表指定位置新增一个元素** @param index* @param e*/@Overridepublic void add(int index, E e) {// 检查index是否越界或数据e是否为空if (checkPositionIndex(index) || assertDataNull(e)) {return;}Node<E> newNode = new Node<>(e, null);// 在头结点处插入if (index == 0) {newNode.next = first;first = newNode;last = newNode;} else if (index == size - 1) {// 在尾部插入newNode.next = first;last.next = newNode;last = newNode;} else {// 在中部插入// 获取指定位置前一个元素Node<E> node = node(index - 1);newNode.next = node.next;node.next = newNode;}size++;}

拓展，在表的末尾插入新结点：

/*** 在链表末尾添加元素** @param e*/@Overridepublic void add(E e) {// 检查数据是否存在if (assertDataNull(e)) {return;}Node<E> newNode = new Node<>(e, null);// 头结点不存在if (isEmpty()) {first = newNode;last = newNode;} else {last.next = newNode;newNode.next = first;last = newNode;}size++;}

删除操作

假设要删除循环链表的第i个结点，那么可能会出现3种情况：

（1）删除表头的结点。表头指针first指向它的link域结点所在的指针；表尾指针last指向新的表头指针；

// 表头指针first指向它的link域结点所在的指针first = first.next;// 表尾指针last指向新的表头指针last = first;

（2）删除表尾的结点。获取删除位置i的前一个结点，即i-1结点；i-1结点link域指向头指针first；尾指针last指向i-1结点；

// 假设node为i-1结点// node结点的link域指向头指针node.next = first;// 尾指针last指向i-1结点last = node;

（3）删除中间的结点。获取删除位置i的前一个结点，即i-1结点；i-1结点的link域指向i结点的link域指向的指针；

// 假设node尾i-1结点// i-1结点的link域指向i结点的link域指向的指针node.next = node.next.next

综上，删除的算法可以总结为：

/*** 移除指定位置的元素** @param index*/@Overridepublic void remove(int index) {// 检查index是否越界if (checkPositionIndex(index)) {return;}// 移除头元素if (index == 0) {first = first.next;last = first;} else if (index == size - 1) {// 移除尾元素// 获取移除元素的前一个Node<E> node = node(index - 1);node.next = first;last = node;} else {// 移除中间的元素// 获取移除元素的前一个Node<E> node = node(index - 1);node.next = node.next.next;}size--;}

3.2.3 循环链表的遍历，清空

获取结点和判空操作与单链表的相同

遍历链表

循环链表的遍历与单链表不一致，因为first指针和last指针指向的是同一个地址，所以需要一些特殊的处理技巧，这里使用do-while循环

/*** 输出环形链表*/@Overridepublic void print() {if(isEmpty()){return;}Node<E> cur = first;do {System.out.print(cur.item + " ");cur = cur.next;} while (cur != first);System.out.println();}

清空链表

/*** 清空链表*/@Overridepublic void clear() {// 循环清空每个结点for (Node<E> x = first; x != null; ) {Node<E> next = x.next;x.item = null;x.next = null;x = next;}first = null;last = null;size = 0;}

3.3 双向链表

使用双向链表的目的是为了解决在链表中访问直接前驱和直接后继的问题。因为双向链表中每个结点都有两个指针，一个指向结点的直接前驱，一个指向结点的直接后继。这样，无论是向前驱搜索或者向后继方向搜索，其时间开销都是O（1）

3.3.1 双向链表的定义

双向链表的结点结构包含了3个部分，lLink指向它的前驱结点，data为数据域，rLink指向它的后继结点

ADT可以表示为：

class Node<E> {E item;Node<E> prev;Node<E> next;}

3.3.2 双向链表的插入和删除

插入操作

假设在数据项ai的后面插入新结点x，情况可能有3种

（1）在链表的表头插入一个新结点。新结点的rLink域指向first；first的lLink域指向新结点；first指向新结点；

newNode.next = first;first.prev = newNode;first = newNode;

（2）在链表的末尾插入一个新结点。找到链表的末尾结点i-1；i-1的rLink域指向新结点；新结点的lLink域指向i-1结点；

// 假设i-1结点为node// i-1的rLink域指向新结点node.next = newNode;newNode.prev = node;

（3）在链表的中间插入一个新结点。找到插入位置的前一个结点，即i-1结点；新结点的rLink指向i-1结点的rLink指向的指针；i-1结点的rLink指向的指针的lLink指向新结点；i-1结点的rLink指向新结点；新结点的lLink指向i-1结点；

// 假设i-1结点为node// 新结点的rLink指向i-1结点的rLink指向的指针newNode.next = node.next;// i-1结点的rLink指向的指针的lLink指向新结点node.next.prev = newNode;// i-1结点的rLink指向新结点node.next = newNode;// 新结点的lLink指向i-1结点newNode.prev = node;

综上，双向链表的插入算法可以总结为：

/*** 在链表的制定位置添加一个元素** @param index* @param e*/@Overridepublic void add(int index, E e) {// 检查index是否越界或数据e是否为空if (checkPositionIndex(index) || assertDataNull(e)) {return;}Node<E> newNode = new Node<>(e, null, null);// 表头为空，添加一个头元素if (index == 0) {// 表头为空if (isEmpty()) {first = newNode;}newNode.next = first;first.prev = newNode;first = newNode;} else if (index == size - 1) {// 在末尾添加Node<E> node = node(index - 1);node.next = newNode;newNode.prev = node;} else {// 在中部添加// 获取添加元素的前一个Node<E> node = node(index - 1);newNode.next = node.next;node.next.prev = newNode;node.next = newNode;newNode.prev = node;}}

删除操作

假设删除第i个位置的数据项，那么有3种情况

（1）删除表头。表头的rLink域指向的指针的lLink置为NULL；表头指针指向它的rLink指向的指针；

// 表头的rLink域指向的指针的lLink置为NULLfirst.next.prev = null;// 表头指针指向它的rLink指向的指针first = first.next;

（2）删除表尾元素。找到删除位置i的前一个结点，即i-1结点；i-1结点的rLink域置为NULL；

// 假设i-1结点为node// node的rLink域置为NULLnode.next = null;

（3）删除中间元素。找到删除位置i的前一个结点，即i-1结点；

// 假设i-1结点为nodenode.next = node.next.next;node.next.next.prev = node;

综上，双向链表的删除算法可以总结为：

/*** 移除链表中指定位置的元素** @param index*/@Overridepublic void remove(int index) {// 检查下标是否越界if (checkPositionIndex(index)) {return;}// 移除头结点if (index == 0) {first.next.prev = null;first = first.next;} else if (index == size - 1) {// 移除尾部元素Node<E> node = node(index - 1);node.next = null;} else {// 移除中部元素Node<E> node = node(index - 1);node.next = node.next.next;node.next.next.prev = node;}size--;}