文档章节

java实现双向链表

淡看江湖
 淡看江湖
发布于 2016/02/05 14:45
字数 504
阅读 207
收藏 8

第一个版本,没有最后一个节点,每次从根节点开始遍历

public class  LinkedList<E> {
     
    private Node head;
     
    public LinkedList() {
    }
     
    public E getFirst(){
        if(head==null){
            return null;
        }
        return head.value;
    }
     
    public LinkedList<E> addFirst(E e){
        head.pre=new Node(e, null, head);
        head=head.pre;
        return this;
    }
     
    public LinkedList<E> addNode(E e){
        Node lst=head;
        if(lst==null){
            this.head=new Node(e, null, null);
            return this;
        }else{
            while(true){
                if(lst.next==null){
                    break;
                }else{
                    lst=lst.next;
                }
            }
            lst.next=new Node(e, lst, null);
            return this;
        }
    }
     
    public LinkedList<E> remove(E e){
        Node lst=head;
        if(lst==null){
            throw new NullPointerException("the LinkedList is empty.");
        }else{
            while(true){
                if(e.equals(lst.value)){
                    //移除这个元素
                    if(lst.pre!=null){
                        lst.pre.next=lst.next;
                    }
                    if(lst.next!=null){
                        lst.next.pre=lst.pre;
                    }
                    lst=null;
                    break;
                }
                lst=lst.next;
            }
            return this;
        }
    }
     
     
    @Override
    public String toString() {
        StringBuffer buff=new StringBuffer("[");
        Node lst=this.head;
        while(lst!=null){
            buff.append(lst.value+",");
            lst=lst.next;
        }
        return buff.substring(0, buff.length()-1)+"]";
    }
     
    /**节点信息*/
    private class Node{
        public Node pre;
        public E value;
        public Node next;
         
        public Node(E value,Node pre,Node next) {
            this.value=value;
            this.pre=pre;
            this.next=next;
        }
    }
     
}

第二个版本,有了最后一个节点

public class  LinkedList<E> {
    
    private Node head;
    private Node last;
    
    public LinkedList() {
    }
    
    public E getFirst(){
        if(head==null){
            return null;
        }
        return head.value;
    }
    public E getLast(){
        if(last==null){
            return null;
        }
        return last.value;
    }
    
    public LinkedList<E> addFirst(E e){
        head.pre=new Node(e, null, head);
        head=head.pre;
        return this;
    }
    
    public LinkedList<E> addNode(E e){
        Node lst=last;
        if(lst==null){//如果最后一个节点是空的则这个链表就是空的
            this.last=new Node(e, null, null);
            this.head=this.last;
            return this;
        }else{
            while(true){
                if(lst.next==null){//
                    break;
                }else{
                    lst=lst.next;
                }
            }
            lst.next=new Node(e, lst, null);
            last=lst.next;
            return this;
        }
    }
    
    public LinkedList<E> remove(E e){
        Node lst=head;
        if(lst==null){
            throw new NullPointerException("the LinkedList is empty.");
        }else{
            while(true){
                if(e.equals(lst.value)){
                    //移除这个元素
                    if(lst.pre!=null){
                        lst.pre.next=lst.next;
                    }
                    if(lst.next!=null){
                        lst.next.pre=lst.pre;
                    }
                    lst=null;
                    break;
                }
                lst=lst.next;
            }
            return this;
        }
    }
    
    
    @Override
    public String toString() {
        StringBuffer buff=new StringBuffer("[");
        Node lst=this.head;
        while(lst!=null){
            buff.append(lst.value+",");
            lst=lst.next;
        }
        return buff.substring(0, buff.length()-1)+"]";
    }
    
    /**节点信息*/
    private class Node{
        public Node pre;
        public E value;
        public Node next;
        
        public Node(E value,Node pre,Node next) {
            this.value=value;
            this.pre=pre;
            this.next=next;
        }
    }
    
}

注:以上两个版本都没有考虑在多线程下使用的情况。

© 著作权归作者所有

共有 人打赏支持
淡看江湖
粉丝 33
博文 82
码字总数 92173
作品 0
浦东
后端工程师
Java_LinkedList_数据结构

java api 在包java.util.LinkedList中有一个LinkedList双向链表类;在由于最近有许多的java课程作业,兴趣之余自己写了一个类似的LinkedList类。由于是从C/C++转向java的,代码中还是有许多C...

掬一捧
2012/04/16
0
0
JDK容器学习之LinkedList:底层存储&读写逻辑

LinkedList的底层结构及读写逻辑 链表容器,通常适用于频繁的新增删除,遍历的方式访问数据元素的场景 LinkedList 底层数据结构为链表,非线程安全,本片博文则简单分析下增删改对链表的操作...

小灰灰Blog
2017/10/20
0
0
使用 LinkedHashMap 实现 LRU 算法

LinkedHashMap 源码分析 上面是 LinkedHashMap 的继承结构。然后看下构造方法: 构造方法比较简单,主要是多个两个成员变量,并且构造方法当中多了 accessOrder。 下面看下 put 方法,Linke...

王爵nice
2015/07/30
0
0
JDK源码之LinkedList

LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实...

村长大神
2014/03/27
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
07/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

八大包装类型的equals方法

先看其中一个源码 结论:八大包装类型的equals方法都是先判断类型是否相同,不相同则是false,相同则判断值是否相等 注意:包装类型不能直接用==来等值比较,否则编译报错,但是数值的基本类型...

xuklc
33分钟前
1
0
NoSQL , Memcached介绍

什么是NoSQL 非关系型数据库就是NoSQL,关系型数据库代表MySQL 对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很耗...

TaoXu
昨天
0
0
890. Find and Replace Pattern - LeetCode

Question 890. Find and Replace Pattern Solution 题目大意:从字符串数组中找到类型匹配的如xyy,xxx 思路: 举例:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"abc ......

yysue
昨天
0
0
Linux | Redis

写在前面的话 常言道,不作笔记不读书。在下是深有体会啊,所以,跟我一起做下本节的笔记吧,或许多年以后,你一定会感谢今天的你。 安装 在官网的下载页 Redis Download 直接写了在Linux的安...

冯文议
昨天
1
0
NoSQL-memcached

NoSQL介绍 NoSQL叫非关系型数据库。而关系型数据库代表有MySQL。对于关系型数据库来说,是需要把数据存储到库、表、行、字段里,查询的时候根据条件一行一行地去匹配,当量非常大的时候就很...

ln97
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部