文档章节

基本数据结构之LinkedList

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/12 20:48
字数 427
阅读 245
收藏 4
点赞 0
评论 0

问题描述: 

LinkedList


问题分析: 

基本的实现


代码实现:

package c03;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @project: DataStructureAndAlgorithmAnalysis
 * @filename: MyLinkedList.java
 * @version: 0.10
 * @author: Jimmy Han
 * @date: 21:56 2015/7/15
 * @comment: Test Purpose
 * @result:
 */
public class MyLinkedList<AnyType> implements Iterable<AnyType>{
    private static class Node<AnyType>{
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
            data = d; prev = p; next = n;
        }
        public AnyType data;
        public Node<AnyType> prev;
        public Node<AnyType> next;
    }

    public MyLinkedList(){doClear();}

    public void clear(){doClear();}

    private void doClear(){
        beginMarker = new Node<AnyType>(null, null, null);
        endMarker = new Node<AnyType>(null, beginMarker, null);
        beginMarker.next = endMarker;

        theSize = 0;
        modCount++;
    }

    public int size(){return theSize;}

    public boolean isEmpty(){return size() == 0;}

    public boolean add(AnyType x){
        add(size(), x); return true;
    }

    public void add(int idx, AnyType x){
        addBefore(getNode(idx, 0, size()), x);
    }

    public AnyType get(int idx){return getNode(idx).data;}

    public AnyType set(int idx, AnyType newVal){
        Node<AnyType> p = getNode(idx);
        AnyType oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }

    public AnyType remove(int idx){
        return remove(getNode(idx));
    }
    private void addBefore(Node<AnyType> p, AnyType x){
        Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        theSize++;
        modCount++;
    }

    private AnyType remove(Node<AnyType> p){
        p.prev.next = p.next;
        p.next.prev = p.prev;
        theSize--;
        modCount++;

        return p.data;
    }

    private Node<AnyType> getNode(int idx){
        return getNode(idx, 0, size() - 1);
    }

    private Node<AnyType> getNode(int idx, int lower, int upper){
        Node<AnyType> p;

        if(idx < lower || idx > upper)
            throw new IndexOutOfBoundsException();

        if(idx < size()/2){
            p = beginMarker.next;
            for(int i = 0; i < idx; i++)
                p = p.next;
        }
        else{
            p = endMarker;
            for(int i = size(); i > idx; i--)
                p = p.prev;
        }
        return p;
    }

    public Iterator<AnyType> iterator(){
        return new LinkedListIterator();
    }

    private class LinkedListIterator implements Iterator<AnyType>{
        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        public boolean hasNext(){
            return current != endMarker;
        }

        public AnyType next(){
            if(modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if(!hasNext())
                throw new NoSuchElementException();

            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }

        public void remove(){
            if(modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if(!okToRemove)
                throw new IllegalStateException();

            MyLinkedList.this.remove(current.prev);
            expectedModCount++;
            okToRemove = false;
        }
    }

    private int theSize;
    private int modCount = 0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;

    public static void main(String[] args) {
        MyLinkedList<String> marr = new MyLinkedList<String>();
        marr.add("www.");
        marr.add("bw");
        marr.add(".com");
        marr.add("s");
        marr.remove(3);
        marr.add(".cn");

        System.out.println(marr.get(2));
        System.out.println(marr.set(1,"hello"));

        printAll(marr.iterator());

    }

    private static void printAll(Iterator<String> iterator) {
        while(iterator.hasNext()){
            String item = iterator.next();
            System.out.print(item);
        }
    }
}


© 著作权归作者所有

共有 人打赏支持
关西大汉弹琵琶
粉丝 7
博文 41
码字总数 14221
作品 0
浦东
程序员
java容器详解(二)Collection与Collections

Collection 表示一组被一个或多个规则约束的对象,这些对象也称为 collection 的元素。一些 collection 允许有重复的元素,而另一些则不允许。一些 collection 是有序的,而另一些则是无序的...

pseudo
2013/06/12
0
0
Java容器类框架分析(2)LinkedList源码分析

概述 在分析LinkedList的源码之前,先看一下ArrayList在数据结构中的位置,常见的数据结构按照逻辑结构跟存储结构可以做如下划分: 数据结构分类 先看看源码的注释: Doubly-linked list imp...

wustor
2017/11/06
0
0
Java集合系列之近乎万能的LinkedList

Java集合系列之近乎万能的LinkedList Hello,大家好,元旦已经过去了,小伙伴们该安心回来工作赚钱了,OK,废话少说,上几篇文章给大家讲了HashMap,ArrayList的底层实现,这一篇给大家讲一讲L...

01/02
0
0
Java集合族谱总结

集合族谱核心成员 集合族谱核心成员 所有的集合类,都实现了Iterator接口,这是用于遍历集合中元素的接口;Java集合框架核心是两个类型的容器,一种是集合(Collection),存储单一元素,一种...

翻滚吧李博
2017/12/19
0
0
集合(二):List接口。

一:List接口: 继承自Collection,如下: 1.ArrayList( 实现类): ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量能动态增长。它继承于AbstractList,实现了L...

牧羊人Berg
2016/05/25
100
0
Java集合,LinkedList底层实现和原理

概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 LinkedList类是L...

郑加威
02/27
0
0
JAVA容器-自问自答学LinkedList

前言 在前一篇文章我以面试问答的形式与大家一同学习了ArrayList,有兴趣但是没阅读过的同学可以翻看我的文章记录,有了ArrayList,自然少不了LinkedList了。 PS:由于我的居住地珠海前两天遭...

liangzzz
2017/08/28
0
0
JDK容器学习之LinkedList:底层存储&读写逻辑

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

小灰灰Blog
2017/10/20
0
0
猎头最爱问的java面试题附答案(三)

1.你了解大O符号(big-O notation)么?你能给出不同数据结构的例子么? 大O符号描述了当数据结构里面的元素增加的时候,算法的规模或者是性能在最坏的场景下有多么好。 大O符号也可用来描述其...

嘿你好夏天
2017/12/30
0
0
JAVA容器-自问自答学LinkedList

前言 在前一篇文章我以面试问答的形式与大家一同学习了ArrayList,有兴趣但是没阅读过的同学可以翻看我的文章记录,有了ArrayList,自然少不了LinkedList了。 PS:由于我的居住地珠海前两天遭...

liangzzz
2017/08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Kafka设计解析(一)- Kafka背景及架构介绍

原创文章,转载请务必将下面这段话置于文章开头处。(已授权InfoQ中文站发布) 本文转发自技术世界,原文链接 http://www.jasongj.com/2015/03/10/KafkaColumn1 摘要   Kafka是由LinkedI...

mskk
8分钟前
0
0
使用Service Mesh整合您的微服务架构

在微服务架构的世界中,它正在达到这样的程度,即管理系统的复杂性对于利用它带来的好处变得至关重要。 目前,如何实现这些微服务不再是一个问题,因为有很多可用的框架(Spring Boot,Vert....

xiaomin0322
11分钟前
0
0
看看 LinkedList Java 9

终于迎来了 LinkedList 类,实现的接口就有点多了 Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>。LinkedList是一个实现了List接口和Deque接口的双端链......

woshixin
29分钟前
0
0
算法 - 冒泡排序 C++

大家好,我是ChungZH。今天我给大家讲一下最基础的排序算法:冒泡排序(BubbleSort)。 冒泡排序算法的原理如下: 比较相邻的元素。如果第一个比第二个大(可以相反),就交换他们两个。 对每...

ChungZH
32分钟前
0
0
jquery ajax request payload和fromData请求方式

请求头的不同 fromData var data = { name : 'yiifaa'};// 提交数据$.ajax('app/', { method:'POST', // 将数据编码为表单模式 contentType:'application/x-ww...

lsy999
34分钟前
0
0
阿里P7架构师,带你点亮程序员蜕变之路

前言: Java是现阶段中国互联网公司中,覆盖度最广的研发语言。 掌握了Java技术体系,不管在成熟的大公司,快速发展的公司,还是创业阶段的公司,都能有立足之地。 有不少朋友问,成为Java架...

Java大蜗牛
36分钟前
1
0
Ecstore 在没有后台管理界面(维护)的情况如何更新表的字段

window 系统: 切换到:app\base 目录下: C:\Users\qimh>d: D:\>cd D:\WWW\huaqh\app\base 执行:D:\WWW\huaqh\app\base>cmd update linux 系统: 1># cd /alidata/www.novoeshop.com/app/......

qimh
40分钟前
0
0
设计模式-策略模式

策略模式 解释 对工厂模式的再次封装,使用参数控制上下文信息(将工厂返回的实例赋值给context field) 不会返回bean实例,只是设置对应的条件 调用context的方法(调用field的方法) 用户只...

郭里奥
43分钟前
0
0
python使用有序字典

python自带的collections包中有很多有用的数据结构可供使用,其中有个叫OrderedDict类,它可以在使用的时候记录元素插入顺序,在遍历使用的时候就可以按照原顺序遍历。 a = {"a":1,"b"...

芝麻糖人
今天
0
0
RestTemplate HttpMessageConverter

RestTemplate 微信接口 text/plain HttpMessageConverter

微小宝
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部