数据结构与算法(五)-线性表之双向链表与双向循环链表

前言:前面介绍了循环链表,虽然循环链表可以解决单链表每次遍历只能从头结点开始,但是对于查询某一节点的上一节点,还是颇为复杂繁琐,所以可以在结点中加入前一个节点的引用,即双向链表

一、简介

双向链表:在链表中,每一个节点都有对上一个节点和下一个节点的引用或指针,即从一个节点出发可以有两条路可选择。

  双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针或引用,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

特性:

  • 遍历可逆性:可以反向遍历;
  • 相比于单链表,循环单链表无论是插入还是遍历,更便利,更快捷;
  • 双向链表可以有效的提高算法的时间性能,说白了就是用空间换时间;

二、双向链表实现

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;
        }

    }
    
}

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++;
    }

 本系列参考书籍:

  《写给大家看的算法书》

  《图灵程序设计丛书 算法 第4版》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏待你如初见

Day10

1502
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

972
来自专栏desperate633

LintCode 线段树系列问题(线段树的构造,线段树的构造||,线段树的查询,线段树的查询II,线段树的修改)线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

833
来自专栏LanceToBigData

JavaSE(八)之集合练习一

前面把Collection家族给学习完毕了,接下来我们通过几个练习来巩固前面的知识。   一、产生10个1-20之间的随机数要求随机数不能重复 import j...

1919
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题15求链表中倒数第K个结点

算法的分析过程均在代码注释中: /** * 题目:输入一个单链表,输出该链表从后往前的第k个数。 * PS:从后往前数时从1开始计数。 * @author...

2956
来自专栏LeetCode

LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the ...

1465
来自专栏禁心尽力

Set容器--HashSet集合

Set容器特点: ①   Set容器是一个不包含重复元素的Collection,并且最多包含一个null元素,它和List容器相反,Set容器不能保证其元素的顺...

2225
来自专栏专注研发

java大数(BigInteger)

 Math类:   java.lang.Math类中包含基本的数字操作,如指数、对数、平方根和三角函数。   java.math是一个包,提供用于执行任意精度整...

3772
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedHashMap

994
来自专栏算法与数据结构

数据结构 链表改进

主要介绍循环链表和双向循环链表 循环链表 双向循环链表 2-1 对于一非空的循环单链表,h和p分别指向链表的头、尾结点,则有() ? 循环单链表判空: 设头结点...

4707

扫码关注云+社区

领取腾讯云代金券