前言
链表是一种 递归 的数据结构,或者为空
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;
}
}
复制
总结
本文从单向链表和双向链表的结构定义出发,然后又分别介绍了如何基于单向链表实现堆和栈,最后则是对双向链表的增删改查进行了总结。对于文中有疏漏的地方,欢迎评论留言。