文档章节

java 数据结构与并发之 --- List (基础篇)

 飞燕candy
发布于 2014/08/04 23:55
字数 2486
阅读 33
收藏 1

java常用的数据结构我们在java.util包下的 如: List, Set, Map 等。这些集合数据结构都继承同一个接口就是Collection:

Method Summary
 boolean add(E e) 
          Ensures that this collection contains the specified element (optional operation).
 boolean addAll(Collection<? extends E> c) 
          Adds all of the elements in the specified collection to this collection (optional operation).
 void clear() 
          Removes all of the elements from this collection (optional operation).
 boolean contains(Object o) 
          Returns true if this collection contains the specified element.
 boolean containsAll(Collection<?> c) 
          Returns true if this collection contains all of the elements in the specified collection.
 boolean equals(Object o) 
          Compares the specified object with this collection for equality.
 int hashCode() 
          Returns the hash code value for this collection.
 boolean isEmpty() 
          Returns true if this collection contains no elements.
 Iterator<E> iterator() 
          Returns an iterator over the elements in this collection.
 boolean remove(Object o) 
          Removes a single instance of the specified element from this collection, if it is present (optional operation).
 boolean removeAll(Collection<?> c) 
          Removes all of this collection's elements that are also contained in the specified collection (optional operation).
 boolean retainAll(Collection<?> c) 
          Retains only the elements in this collection that are contained in the specified collection (optional operation).
 int size() 
          Returns the number of elements in this collection.
 Object[] toArray() 
          Returns an array containing all of the elements in this collection.
     
<T> T[]
toArray(T[] a) 
          Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.

Method Summary
 boolean add(E e) 
          Ensures that this collection contains the specified element (optional operation).
 boolean addAll(Collection<? extends E> c) 
          Adds all of the elements in the specified collection to this collection (optional operation).
 void clear() 
          Removes all of the elements from this collection (optional operation).
 boolean contains(Object o) 
          Returns true if this collection contains the specified element.
 boolean containsAll(Collection<?> c) 
          Returns true if this collection contains all of the elements in the specified collection.
 boolean equals(Object o) 
          Compares the specified object with this collection for equality.
 int hashCode() 
          Returns the hash code value for this collection.
 boolean isEmpty() 
          Returns true if this collection contains no elements.
 Iterator<E> iterator() 
          Returns an iterator over the elements in this collection.
 boolean remove(Object o) 
          Removes a single instance of the specified element from this collection, if it is present (optional operation).
 boolean removeAll(Collection<?> c) 
          Removes all of this collection's elements that are also contained in the specified collection (optional operation).
 boolean retainAll(Collection<?> c) 
          Retains only the elements in this collection that are contained in the specified collection (optional operation).
 int size() 
          Returns the number of elements in this collection.
 Object[] toArray() 
          Returns an array containing all of the elements in this collection.
     
<T> T[]
toArray(T[] a) 
          Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.

Collection 接口定义了以上通用的接口方法,同时继承了Iterable接口:

 Iterator<T> iterator() 
          Returns an iterator over a set of elements of type T.

使得Collection下的所有实现类都可以通过自己的实现通过通用的iterator方法进行遍历。

今天首先要学习一下List:(除了Collection中的方法,List多定义了如下几个方法)

 void add(int index, E element) 
          Inserts the specified element at the specified position in this list (optional operation).
 E get(int index) 
          Returns the element at the specified position in this list.
 int indexOf(Object o) 
          Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
 int lastIndexOf(Object o) 

          Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.

 ListIterator<E> listIterator() 
          Returns a list iterator over the elements in this list (in proper sequence).
 ListIterator<E> listIterator(int index) 
          Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.
 E remove(int index) 
          Removes the element at the specified position in this list (optional operation).
 E set(int index, E element) 
          Replaces the element at the specified position in this list with the specified element (optional operation).
 E set(int index, E element) 
          Replaces the element at the specified position in this list with the specified element (optional operation).
 List<E> subList(int fromIndex, int toIndex) 
          Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

可以看出多出来的方法几乎都和 index 相关的集合操作 和 listIterator 方法,说明了List是一个和 index(下标)有着重要关系的结合,而我们知道我们经常用到的ArrayList和LinkedList都实现了这些方法。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> 

从 AbstractList 定义里我们基本可以看出,AbstractList 实现了List的部分接口方法,和继承了AbstractCollection 实现的Collection的基本方法。其中AbstractCollection实现了Collection接口里的大部分方法,其中这些方法的遍历都是通过Iterator的方式进行的,以下两个方法是未实现的方法而其他已经实现的方法中都用到的方法

public abstract Iterator<E> iterator();

public abstract int size();

另外一个add方法强制了一个为实现的异常:

public boolean add(E e) {

    throw new UnsupportedOperationException();

}

AbstractList 通过 listIterator 和 iterator 方法实现了其中关于index位置和集合的操作,基本的set ,add, remove等都强制用了异常实现,get没有实现。

其中 AbstractList 中更有两个内部类 Itr 实现了 Iterator接口 和  ListItr 继承 Itr 和 实现了 ListIterator接口。

Iterator接口:

Method Summary
 boolean hasNext() 
          Returns true if the iteration has more elements.
 E next() 
          Returns the next element in the iteration.
 void remove() 
          Removes from the underlying collection the last element returned by the iterator (optional operation).

从 Itr中的源码我们可以看出,实现比较简单,主要通过维护当前的 cursor 和上一次返回数据的lastRet位置来实现。同时next和remove的时候都进行了checkForComodification检查。这说明继承 AbstractList的数据结构在维护的exceptedModCount != modCount 的时候就抛出异常。基本上Iterator的实现还是基于原数据结构的get(index), remove(index) 等方法,还有之所以Iterator方式remove比遍历安全的的原因,iterator能够感知目前数据结构的实时长度。

private class Itr implements Iterator<E> {
	/**
	 * Index of element to be returned by subsequent call to next.
	 */
	int cursor = 0;

	/**
	 * Index of element returned by most recent call to next or
	 * previous.  Reset to -1 if this element is deleted by a call
	 * to remove.
	 */
	int lastRet = -1;

	/**
	 * The modCount value that the iterator believes that the backing
	 * List should have.  If this expectation is violated, the iterator
	 * has detected concurrent modification.
	 */
	int expectedModCount = modCount;

	public boolean hasNext() {
            return cursor != size();
	}

	public E next() {
            checkForComodification();
	    try {
		E next = get(cursor);
		lastRet = cursor++;
		return next;
	    } catch (IndexOutOfBoundsException e) {
		checkForComodification();
		throw new NoSuchElementException();
	    }
	}

	public void remove() {
	    if (lastRet == -1)
		throw new IllegalStateException();
            checkForComodification();

	    try {
		AbstractList.this.remove(lastRet);
		if (lastRet < cursor)
		    cursor--;
		lastRet = -1;
		expectedModCount = modCount;
	    } catch (IndexOutOfBoundsException e) {
		throw new ConcurrentModificationException();
	    }
	}

	final void checkForComodification() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	}
    }

ListIterator 接口继承 Iterator接口,多出了具有List序列特性的方法:

Method Summary
 void add(E e) 
          Inserts the specified element into the list (optional operation).
 boolean hasNext() 
          Returns true if this list iterator has more elements when traversing the list in the forward direction.
 boolean hasPrevious() 
          Returns true if this list iterator has more elements when traversing the list in the reverse direction.
 E next() 
          Returns the next element in the list.
 int nextIndex() 
          Returns the index of the element that would be returned by a subsequent call to next.
 E previous() 
          Returns the previous element in the list.
 int previousIndex() 
          Returns the index of the element that would be returned by a subsequent call to previous.
 void remove() 
          Removes from the list the last element that was returned by next or previous (optional operation).
 void set(E e) 
          Replaces the last element returned by next or previous with the specified element (optional operation).

可以看出ListItr 实现了 ListIterator定义的其他的另外几个方法啊,同理都使用了原数据结构中的方法实现完成,同时表现力多出了可以从某个位置遍历和向前遍历等方法。由此可以看出使用List数据结构的时候使用ListIterator接口的遍历方案有更强的变现能力。

    private class ListItr extends Itr implements ListIterator<E> {
	ListItr(int index) {
	    cursor = index;
	}

	public boolean hasPrevious() {
	    return cursor != 0;
	}

        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

	public int nextIndex() {
	    return cursor;
	}

	public int previousIndex() {
	    return cursor-1;
	}

	public void set(E e) {
	    if (lastRet == -1)
		throw new IllegalStateException();
            checkForComodification();

	    try {
		AbstractList.this.set(lastRet, e);
		expectedModCount = modCount;
	    } catch (IndexOutOfBoundsException ex) {
		throw new ConcurrentModificationException();
	    }
	}

	public void add(E e) {
            checkForComodification();

	    try {
		AbstractList.this.add(cursor++, e);
		lastRet = -1;
		expectedModCount = modCount;
	    } catch (IndexOutOfBoundsException ex) {
		throw new ConcurrentModificationException();
	    }
	}
   }

值得注意的是 AbstractList 有一个 subList 方法,由于 AbstractList 是抽象类无法实现的类,所以必须使用了子类的内部类SubList 和 RandomAccessSubList 实现 AbstractList,最终还是调用了 AbstractList 中的未实现的方法,所以可以看出此种实现仍然是通过装饰者的方式依赖最终实现类。

AbstractList 对 hashcode 和 equals方法都进行了重写来符合List的具体情况。

下面来看一下 AbstractList 的几个我们常用的实现类  ArrayList , Vector 和 LinkedList 

ArrayList 和 Vector 我们基本可以理解成是自动扩展的线性数组的同步和非同步实现方式,但是从两个类的代码中可以看出实际上可能是出于性能的考虑,他们都重写了很多 AbstractCollection 和 AbstractList中已经实现过的方法,使得已经实现的抽象在考虑具体性能的时候进行了重写,毕竟依赖Iterator和ListIterator的抽象在具体的实现要考虑性能的时候并不是那么的完美。

Vector 的方法都使用了synchronized 来保证竞争的时候数据是安全的,因为它的方法执行是同步的,而ArrayList是线程非安全的。他们都维护了一个elementData数组,通过默认构造器的默认都是创建10个元素,通过ensureCapacity扩容,不同的是 Vector 使用 * 2 的方式增长,而 ArrayList 通过 *1.5+1 的方式进行增长。

Collections 类中提供了 synchronizedCollection 和 synchronizedList 方法分别来返回 内部静态类 SynchronizedCollection 和  SynchronizedList(SynchronizedRandomAccessList)的实例, SynchronizedList(SynchronizedRandomAccessList)继承自 SynchronizedCollection 类, 他们实现的同步的方式是使用 final Object mutex 对象变量,分别对每个接口的方法进行包装,在方法外层对mutex对象进行同步化处理,同样是“装饰者”模式的一个使用。 

另外 Collections 类中还提供了  UnmodifiableCollection 和 UnmodifiableList 方法分别返回内部静态类 UnmodifiableCollection 和 UnmodifiableList(UnmodifiableRandomAccessList)的实例,同样UnmodifiableList(UnmodifiableRandomAccessList)继承自UnmodifiableCollection类, 他们实现的针对 内部的修改方法 和  Iterator, ListIterator涉及修改内部结构的方法全部进行了异常抛出而达到不能修改的目的。

LinkedList 继承自 AbstractSequentialList --> AbstractList, AbstractSequentialList实现了 其他方法,只留下了 listIterator 抽象方法。LinkedList 的实现基本上依托内部类  Entry 的实现,方法基本上都通过链式的结构进行重新实现的,重新实现了ListItr 类 ,同样使用Entry进行了重新实现其内部方法。java1.6提供了 descendingIterator 方法 和 DescendingIterator 类,同时也是用新的ListItr来进行实现,主要用于向前遍历。




© 著作权归作者所有

粉丝 0
博文 3
码字总数 6793
作品 0
浦东
私信 提问
本地方法怎么映射Java层的数据类型

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/wangyangzhizhou/article/details/79576578 前言 Java 语言上定义了不同的数据类型,比如有基础类型、等等,还...

超人汪小建(seaboat)
2018/03/16
0
0
Java 10大优点—Part4—Java内存模型

在忙着参加在爱沙尼亚进行的 TEDx talk 演讲活动以及在比利时举办的一届非常忙碌的Devoxx 会议的间隙,我将继续推进 Java’s Rocking 的系列博文。 对还没有接触过这个系列博文的读者,不妨先...

foxlee
2013/12/09
412
1
读书笔记之《Java并发编程的艺术》-并发编程容器和框架(重要)

读书笔记部分内容来源书出版书,版权归本书作者,如有错误,请指正。 欢迎star、fork,读书笔记系列会同步更新 git https://github.com/xuminwlt/j360-jdk module j360-jdk-thread/me.j360....

Hi徐敏
2015/11/11
696
1
求你了,再问你Java内存模型的时候别再给我讲堆栈方法区了…

GitHub 4.1k Star 的Java工程师成神之路 ,不来了解一下吗? GitHub 4.1k Star 的Java工程师成神之路 ,真的不来了解一下吗? GitHub 4.1k Star 的Java工程师成神之路 ,真的确定不来了解一下吗...

Hollis
07/02
0
0
【死磕Java并发】—– 死磕 Java 并发精品合集

【死磕 Java 并发】系列是 LZ 在 2017 年写的第一个死磕系列,一直没有做一个合集,这篇博客则是将整个系列做一个概览。 先来一个总览图: 【高清图,请关注“Java技术驿站”公众号,回复:脑...

chenssy
2018/07/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

查看线上日志常用命令

cat 命令(文本输出命令) 通常查找出错误日志 cat error.log | grep 'nick' , 这时候我们要输出当前这个日志的前后几行: 显示file文件里匹配nick那行以及上下5行 cat error.log | grep -C ...

xiaolyuh
13分钟前
3
0
六、Java设计模式之工厂方法

工厂方法定义: 定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行 类型:创建型 工厂方法-使用场景: 创建对象需要大量重复的代码 ...

东风破2019
20分钟前
2
0
win服务器管理遇到的一系列问题记录

有些小伙伴在使用iis7远程桌面管理工具的时候总是会遇到一系列的问题,下面就是为大家介绍一下服务器日常管理过程中出现的问题及我的解决办法和心得。希望能帮到大家。   拒绝服务器重新启...

1717197346
27分钟前
2
0
flutter 剪切板 复制粘贴

复制粘贴功能 import 'package:flutter/services.dart'; Clipboard.setData(ClipboardData(text:_text));Clipboard.getData;...

zdglf
30分钟前
3
0
如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题?

面试题 如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题? 面试官心理分析 这个是肯定的,用 MQ 有个基本原则,就是数据不能多一条,也不能少一条,不能多,就是前面说的重复消费...

米兜
30分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部