链表解惑
原创大约 7 分钟数据结构与算法链表数据结构
链表解惑
前言
链表是一种 递归 的数据结构，或者为空 null，或者指向一个结点（node）的引用，一个结点含有 一个泛型元素和一个指向另一条链表的引用。
通常分为如下三种类型：
- 单向链表：结点被分成两个部分。第一个部分保存或者显示关于结点的信息，第二个部分存储下一个结点的地址，只能向一个方向遍历。
- 双向链表：每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
- 循环链表：一种 链式存储结构，它的最后一个结点指向头结点，形成一个环。
单向链表
单向链表包括一个值和一个指向下一结点的指针，其典型结构定义如下：
public class Node{
// 数据对象
private Object val;
// 指向后继结点
private Node next;
// 无参构造函数
public Node(){
// 指向数据对象和后继结点的引用都置空
this.val = null;
this.next = null;
}
// 有参构造函数
public Node(Object val, Node node){
this.val = val;
this.next = node;
}
// 获取当前存放位置的数据对象
public Object getVal(){
return this.val;
}
// 将给定元素存放至当前位置，同时返回此前存放的数据对象
public Object setVal(Object value){
Object oldVal = this.val;
this.val = value;
return oldVal;
}
// 取当前结点后继结点
public Node getNext(){
return this.next;
}
// 修改当前结点后继结点
public void setNext(Node newNext){
this.next = newNext;
}
}
双向链表
每个数据结点中都有两个指针，分别指向直接后继和直接前驱，其典型结构定义如下：
public class DoubleNode{
// 数据对象
private Object val;
// 指向前驱结点
private DoubleNode prev;
// 指向后继结点
private DoubleNode next;
// 无参构造函数
public DoubleNode(){
this.val = null;
this.prev = null;
this.next = null;
}
// 有参构造函数
public DoubleNode(Object value, DoubleNode previous, DoubleNode next){
this.val = value;
this.prev = previous;
this.next = next;
}
// 获取当前位置数据对象
public Object getVal(){
return val;
}
// 将给定元素放在当前位置，返回此前存放的元素
public Object setVal(Object value){
Object oldVal = val;
val = value;
return oldVal;
}
// 获取当前结点后继结点
public DoubleNode getNext(){
return next;
}
// 修改后继结点
public void setNext(DoubleNode newNext){
next = newNext;
}
// 获取当前位置前驱结点
public DoubleNode getPrev(){
return prev;
}
// 修改前驱结点
public void setPrev(DoubleNode newPrev){
prev = newPrev;
}
}
单向链表的增删改查
基于链表实现栈
public class MyStack{
// 指向栈顶元素（头结点）
private Node head;
// 栈中元素数目
private int size;
// 构造方法（构造一个空栈）
public MyStack(){
this.head = null;
this.size = 0;
}
// 查询栈中元素个数
public int getSize(){
return size;
}
// 判断栈是否为空
public boolean isEmpty(){
return head == null;
// 或者 size == 0;
}
// 读取栈顶（首结点信息）
public Object getTop(){
if(isEmpty()){
System.out.println("栈空");
}
return head.getVal();
}
// 压栈（即插入首结点）
public void insertAtHead(Object val){
// 创建一个新结点，将其作为首结点插入
Node node = new Node(val, head);
// 更新首结点引用
head = node;
// 栈中元素数目增加
size++;
}
// 出栈（删除首结点）
public Object removeAtHead(){
if(isEmpty){
System.out.println("栈空");
}
// 当前结点数据对象
Object tmp = head.getVal();
// 更新首结点引用
head = head.getNext();
size--;
return tmp;
}
}
基于链表实现队列
public class MyQueue{
// 队列首元素（首结点）
private Node head;
// 队列尾元素（尾结点）
private Node tail;
// 队列规模
private int size;
// 构造空队列
public MyQueue(){
head = null;
tail = null;
size = 0;
}
// 队列规模
public int getSize(){
return size;
}
// 判断当前队列是否为空
public boolean isEmpty(){
return size == 0;
}
// 查看队首元素
public Object getFront(){
if(isEmpty()){
System.out.println("队列为空");
}
return head.getElem();
}
// 入队
public void enQueue(Object val){
Node node = new Node();
// 新结点作为末结点插入
node.setVal(val);
node.setNext(null);
// 若当前队列为空，则直接插入
if(size == 0){
head = node;
}else {
// 否则将新结点接至队列末端
tail.setNext(node);
}
// 更新指向末结点的引用
tail = node;
// 更新队列规模
size++;
}
// 出队
public Object deQueue(){
if(size == 0){
System.out.println("队列为空");
}
Object tmp = head.getVal();
head = head.getNext();
// 更新队列规模
size--;
// 队列为空时，将末结点引用置空
if(size == 0){
tail = null;
}
return tmp;
}
// 遍历队列
public void traversal(){
Node node = head;
while(node != null){
System.out.println(node.getVal() + "\t");
node = node.getNext();
}
}
}
双向链表的增删改查
实现双向链表时，通常在最前端和最后端各设置一个 哑元结点，分别称为 头结点 和 尾结点，起着 哨兵 的作用。但实际上两者并不存储任何实质的数据对象，头（尾）结点的 next（prev）引用指向首（末）结点，而 prev（next）引用为空。
首尾结点的插入
假设要进行首结点的插入，则通常需要如下步骤，而末结点的插入则是和首结点的插入过程对称。
- 首先生成一个新结点；
- 然后将其接入队列的前端；
- 接着将头结点的
next的引用指向新插入的结点，同时将首结点的prev的引用指向新插入的结点。
首尾结点的删除
假设要进行末结点的删除，通常需要如下步骤，而首结点的删除过程适合尾结点的删除过程对称。
- 将新的末结点的
next引用指向尾结点； - 同时将尾结点的
prev引用指向新的末结点； - 最后原先的末结点将会被系统回收。
一般结点的插入与删除
要实现在一般结点之间插入新结点，通常需要进行如下步骤：
- 创建一个新的结点，然后将其
prev引用指向前一个结点，同时将其next引用指向后一个结点； - 然后将前一个结点的
next引用指向新结点，同时将后一个结点的prev引用指向新结点。
而要实现在一般结点之间删除结点，通常需要进行如下步骤：
- 首先找到要删除的结点的前驱和后继结点；
- 然后将其前驱结点的
next引用指向后驱结点，同时将后驱结点的prev引用指向前驱结点。
public class MyDoubleQueue{
// 指向头结点（哨兵）
private DoubleNode header;
// 指向尾结点（哨兵）
private DoubleNode trailer;
// 队列规模
private int size;
// 无参构造函数
public MyDoubleQueue(){
header = new DoublNode();
trailer = new DoubleNode();
header.setNext(trailer);
trailer.setPrev(trailer);
size = 0;
}
// 获取当前队列规模
public int getSize(){
return size;
}
// 判断队列是否为空
public boolean isEmpty(){
return size == 0;
}
// 取首元素
public Object getHead(){
if(isEmpty()){
System.out.println("队列为空");
}
return header.getNext().getVal();
}
// 取末元素
public Objecct getTrail(){
if(isEmpty()){
System.out.println("队列为空");
}
return trailer.getPrev().getVal();
}
// 遍历
public void traversal(){
DoubleNode node = header.getNext();
while(node != trailer){
System.out.print(node.getVal() + "\t");
node = node.getNext();
}
System.out.println();
}
// 前端插入新结点
public void insertFirst(Object val){
DoubleNode second = header.getNext();
DoubleNode first = new DoubleNode(val, header, second);
second.setPrev(first);
header.setNext(first)
size++;
}
// 前端删除结点
public Object removeFirst(){
if(isEmpty()){
System.out.println("队列为空");
}
// first 是要删除的结点，找到要删除结点的后继结点 second
DoubleNode first = header.getNext();
DoubleNode second = first.getNext();
// 要删除结点的值
Object value = first.getVal();
// 将头结点的 next 指向要删除的后继结点 second，同时将 second 的前驱结点指向头结点
header.setNext(second);
second.setPrev(header);
// 更新规模
size--;
return value;
}
// 后端插入新结点
public void insertLast(Object val){
DoubleNode second = trailer.getPrev();
DoubleNode first = new DoubleNode(val, second, trailer);
second.setNext(first);
trailer.setPrev(first);
size++;
}
// 后端删除结点
public Object removeLast(){
if(isEmpty()){
System.out.println("队列为空");
}
DoubleNode first = trailer.getPrev();
DoubleNode second = first.getPrev();
// 要删除结点的值
Object value = first.getVal();
// 将尾结点的 prev 指向要删除的前驱结点 second，同时将 second 的后继结点指向尾结点
trailer.setPrev(second);
second.setNext(trailer);
// 更新规模
size--;
return value;
}
}
总结
本文从单向链表和双向链表的结构定义出发，然后又分别介绍了如何基于单向链表实现堆和栈，最后则是对双向链表的增删改查进行了总结。对于文中有疏漏的地方，欢迎评论留言。如果你觉得文章对你有所帮助，那就点个赞再走吧！