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