前言: 前面介绍了循环链表, 虽然循环链表可以解决单链表每次遍历只能从头结点开始, 但是对于查询某一节点的上一节点, 还是颇为复杂繁琐, 所以可以在结点中加入前一个节点的引用, 即双向链表
一, 简介
双向链表: 在链表中, 每一个节点都有对上一个节点和下一个节点的引用或指针, 即从一个节点出发可以有两条路可选择.
双向链表也叫双链表, 是链表的一种, 它的每个数据结点中都有两个指针或引用, 分别指向直接后继和直接前驱. 所以, 从双向链表中的任意一个结点开始, 都可以很方便地访问它的前驱结点和后继结点. 一般我们都构造双向循环链表.
特性:
遍历可逆性: 可以反向遍历;
相比于单链表, 循环单链表无论是插入还是遍历, 更便利, 更快捷;
双向链表可以有效的提高算法的时间性能, 说白了就是用空间换时间;
二, 双向链表实现
1, 创建节点类 Node, 其中有三个属性 pre,object,next,pre 为上一个节点的引用, 也叫作前驱节点, object 存储数据, next 为下一个节点的引用, 也叫作后继节点:
- public class BothwayLoopChain<T> {
- // 头结点直接引用
- private Node<T> head;
- // 链长度
- private Integer size;
- // 初始化
- BothwayLoopChain() {
- head = new Node<T>();
- head.setNext(null);
- size = 0;
- }
- class Node<T> {
- private Node<T> pre;
- private Object object;
- private Node<T> next;
- public Node<T> getPre() {
- return pre;
- }
- public void setPre(Node<T> pre) {
- this.pre = pre;
- }
- public Object getObject() {
- return object;
- }
- public void setObject(Object object) {
- this.object = object;
- }
- public Node<T> getNext() {
- return next;
- }
- public void setNext(Node<T> next) {
- this.next = next;
- }
- }
- }
BothwayLoopChain.java
2, 获取位置的结点:
- public T get(Integer index) throws Exception {
- return (T) getNode(index).getObject();
- }
- private Node<T> getNode(Integer index) throws Exception {
- if (index> size || index <0) {
- throw new Exception("index outof length");
- }
- Node<T> p = head;
- for (int i = 0; i <index; i++) {
- p = p.next;
- }
- return p;
- }
3, 插入节点:
- // 在尾节点后插入节点
- public void add(T t) throws Exception {
- this.add(t,size);
- }
- // 在 index 位置后插入一个节点
- public void add(T t, Integer index) throws Exception {
- // 创建新节点
- Node<T> p = new Node<>();
- p.setObject(t);
- // 获取该位置的节点
- Node<T> s = getNode(index);
- p.setPre(s);
- if (s.getNext() != null) {
- // 将本节点的 next 节点放入新节点的 next 节点
- p.setNext(s.getNext());
- s.getNext().setPre(p);
- } else {
- p.setNext(null);
- }
- size++;
- }
4, 移除节点:
- // 移除节点并返回
- public Node<T> remove(Integer index) throws Exception {
- // 获取该位置的节点
- Node<T> s = getNode(index);
- // 获取该位置节点的下一个节点
- Node<T> next = s.getNext();
- // 将本节点的 pre 节点的 next 节点设置为 next
- s.getPre().setNext(next);
- next.setPre(s.getPre());
- return s;
- }
至此, 双向链表的基本实现已完成, 其实它就是用空间换时间来提高性能的;
之前了解了单链表的循环结构即单向循环链表, 举一反三, 双向链表也有循环结构, 即双向循环链表;
三, 双向链表扩展 - 双向循环链表
在双向链表的基础上进行改造:
尾节点的 next 指向头结点;
头结点的 pre 指向尾节点;
除了插入方法, 其他方法可保持不变:
- // 在 index 位置后插入一个节点
- public void add(T t, Integer index) throws Exception {
- // 创建新节点
- Node<T> p = new Node<>();
- p.setObject(t);
- // 获取该位置的节点
- Node<T> s = getNode(index);
- p.setPre(s);
- // 将本节点的 next 节点放入新节点的 next 节点
- p.setNext(s.getNext());
- s.getNext().setPre(p);
- size++;
- }
来源: https://www.cnblogs.com/lfalex0831/p/9674349.html