资讯专栏INFORMATION COLUMN

数据结构之双向链表(java版)

legendaryedu / 1042人阅读

摘要:记得在一个公司面试上有一道题,写一个双向链表,包含链表的基本操作,插入,删除,获取长度等操作,由于时间匆忙,代码写的比较乱,连自己都没眼看了,后来细想自己从来都没有细心的写过数据结构,总觉得只要原理明白了就万事大吉了,事实证明,理论和实践还

记得在一个公司面试上有一道题,写一个双向链表,包含链表的基本操作,插入,删除,获取长度等操作,由于时间匆忙,代码写的比较乱,连自己都没眼看了,后来细想自己从来都没有细心的写过数据结构,总觉得只要原理明白了就万事大吉了,事实证明,理论和实践还是有很大差距的。
水平有限,如果有错误,还请不吝赐教

定义一个内部类Node用于存储节点元素
class Node {
     private Node previous;//前驱节点
     private Node next;//后继节点
     private E e;//泛型元素值
     public Node(Node previous, Node next, E e) {
         this.previous = previous;
         this.next = next;
         this.e = e;
    }
双向链表的关键在于节点指针的转移

下面以removeElement(E value)为例简单介绍

    public void removeElement(E value){
        Node index=this.first;//创建index节点指向first节点
        while(index!=null){
            if(index.e==value)break;
            index=index.next;
        }//while循环用于遍历整个链表来获取指向要删除的节点指针
        index.previous.next=index.next;
        index.next.previous=index.previous;
        length--;
    }

index.previous表示要删除节点的前驱节点
index.previous.next=index.next;意思是将前驱节点的后项指针指向要删除节点的后继节点

同理index.next表示要删除节点的后继节点
index.next.previous=index.previous;意思是将后继节点的前向指针指向要删除节点的前驱节点
可能有点绕,简单画个链表结构图就可以很明了了

insertNext(E baseElement,E value)insertPrevious(E baseElement,E value)同理,这里不再赘述

DoubleLinkedList包含两个节点指针(伪指针,java中没有指针的概念)first和last,分别指向链表的第一个元素和最后一个元素

整体代码
public class DoubleLinkedList {
    private Node first;//指向第一个元素
    private Node last;//指向最后一个元素
    private int length=0;//链表长度
    class Node {
        private Node previous;
        private Node next;
        private E e;

        public Node(Node previous, Node next, E e) {
            this.previous = previous;
            this.next = next;
            this.e = e;
        }
    }
    /***
     * 向头节点添加元素,节点结构对外应该是不可见的,所以这里只传递一个泛型的值e
     */
    public void addFirst(E e) {
        if (first == null) {//链表为空判断
            Node node = new Node(null, null, e);//创建一个新的节点,前驱和后继都为空
            this.first = node;
            this.last=node;//将first和last指针指向链表的第一个元素
            length++;//链表长度自增一,下同
        }else{
            Node node=new Node(null,first,e);//链表不为空创建一个前驱为空,后继为当前first节点的节点,值为传入的参数e
            this.first.previous=node;//当前first的前驱设置为node
            this.first=node;//将first指针指向新节点
            length++;
        }
    }
/***
*addLast同addFirst
*/
    public void addLast(E e) {
        if (last == null) {
            Node node = new Node(null, null, e);
            this.first = node;
            this.last=node;
            length++;
        }else{
            Node node=new Node(last,null,e);
            this.last.next=node;
            this.last=node;
            length++;
        }
    }
    public void insertPrevious(E baseElement,E value){
        Node index=this.first;
        while(index!=null){
            if(index.e==baseElement)break;
            index=index.next;
        }
        Node insertValue=new Node(index.previous,index,value);
        index.previous.next=insertValue;
        index.previous=insertValue;
        length++;
    }
    public void insertNext(E baseElement,E value){
        Node index=this.first;
        while(index!=null){
            if(index.e==baseElement)break;
            index=index.next;
        }
        Node insertValue=new Node(index,index.next,value);
        index.next.previous=insertValue;
        index.next=insertValue;
        length++;
    }
    public void removeElement(E value){
        Node index=this.first;
        while(index!=null){
            if(index.e==value)break;
            index=index.next;
        }
        index.previous.next=index.next;
        index.next.previous=index.previous;
        length--;
    }
    public int getLength(){
        return length;
    }
    @Override
    public String toString() {
        StringBuffer sb=new StringBuffer();
        Node current=this.first;
        while(current!=null){
            sb.append(current.e+"->");
            current=current.next;
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        DoubleLinkedList list=new DoubleLinkedList<>();
        list.addLast("value1");
        list.addLast("value2");
        list.addLast("value3");
        list.addLast("value4");
        list.addFirst("value0");
        list.insertPrevious("value3","insertValue");
        list.insertNext("value3","insertValue2");
        System.out.println(list.toString());
        System.out.println("链表的长度是"+list.getLength());
        list.removeElement("value3");
        System.out.println(list.toString());
        System.out.println("链表的长度是"+list.getLength());
    }
}
如果不太了解双向链表的结构可以在纸上画出每个Node以及指向关系

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66831.html

相关文章

  • Java集合LinkedHashMap源码解析

    摘要:底层基于拉链式的散列结构,并在中引入红黑树优化过长链表的问题。在其之上,通过维护一条双向链表,实现了散列数据结构的有序遍历。 原文地址 LinkedHashMap LinkedHashMap继承自HashMap实现了Map接口。基本实现同HashMap一样,不同之处在于LinkedHashMap保证了迭代的有序性。其内部维护了一个双向链表,解决了 HashMap不能随时保持遍历顺序和插...

    QiShare 评论0 收藏0
  • 这几道Java集合框架面试题在面试中几乎必问

    摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

    bigdevil_s 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<