文档章节

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

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

© 著作权归作者所有

共有 人打赏支持
淡看江湖
粉丝 35
博文 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
Vector、ArrayList、LinkedList 有什么区别?

版权声明:本文供交流学习,能够帮助到你是我最大的荣幸! https://blog.csdn.net/u014231523/article/details/82086185 这个问题主要是考察集合框架的问题,主要考察三者之间的设计区别,以...

兴国First
08/26
0
0
Redis学习笔记之基本数据结构

Redis基础数据结构 Redis有5种基本数据结构:String(字符串)、list(列表)、set(集合)、hash(哈希)、zset(有序集合) 字符串string 字符串类型是Redis的value最简单的数据结构,类似与Java语言...

smileNicky
09/26
0
0
使用 LinkedHashMap 实现 LRU 算法

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

王爵nice
2015/07/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java动态代理之InvocationHandler最简单的入门教程

网上关于Java的动态代理,Proxy和InvocationHandler这些概念有讲解得非常高深的文章。其实这些概念没有那么复杂。现在咱们通过一个最简单的例子认识什么是InvocationHandler。值得一提的是,...

JerryWang_SAP
9分钟前
0
0
oracle 在 MyBatis 中使用 like

两种使用方法 使用oracle自带 || 拼凑的方式 <if test="userName!=null and userName!=''"> AND u.USER_NAME like '%' || #{userName} || '%' </if> 使用MyBatis的$符号的方式 <if test="us......

karma123
15分钟前
0
0
带接口的webservice方式发布

package cn.it.ws.e;import javax.jws.WebService;/** * 面向接口的webservice发布方式 * @author Administrator * */@WebServicepublic interface JobService {publi...

江戸川
31分钟前
0
0
day122-20181020-英语流利阅读-待学习

蜘蛛侠新片《毒液》来袭!导演灵感来自哪? Roxy 2018-10-20 1.今日导读 你还记得漫威宇宙中飞檐走壁的蜘蛛侠小可爱吗?在刚过去的国庆黄金周里,索尼影业发行的漫威超级英雄蜘蛛侠系列大片《...

飞鱼说编程
41分钟前
3
0
美团点评Docker容器管理平台

美团点评容器平台简介 本文介绍美团点评的Docker容器集群管理平台(以下简称“容器平台”)。该平台始于2015年,是基于美团云的基础架构和组件而开发的Docker容器集群管理平台。目前该平台为...

Skqing
47分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部