Java教程

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

本文主要是介绍数据结构与算法(五)-线性表之双向链表与双向循环链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

一、简介

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

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

   特性:

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

二、双向链表实现

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

  

 

这篇关于数据结构与算法(五)-线性表之双向链表与双向循环链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!