Java集合(4)——Map

写在开始

每当想要使用键值对存储数据的时候,总能想到Map,现在我们就来看下它的实现原理。本章会讲解HashMap、TreeMap、EnumMap、HashTable。

Java集合的结构图

Map

首先上结构图:

从上面的图可以看出,所有的Map都直接或者间接实现了Map接口,同时也定义了基本的抽象实现AbstractMap。

官方对Map的描述如下:

一个能够将键映射到值的对象。不允许存在两个相同的键,并且一个键理论上只能对应一个值。

注意以下两点:

  • Map在JDK1.2的时候才加入,在此之前,只有基本的抽象类Dictionary。1.2之后,推荐实现Map接口替代Dictionary(类型的协议比类型的抽象更为重要)。
  • 通过Map,我们能够获取到至少3种集合:包含所有键的集合、包含所有值的集合、包含所有键值对的集合。

定义了如下方法:

int size() 获取集合中元素的大小
boolean isEmpty() 检测集合中是否有元素,返回布尔值
boolean containsKey(Object key) 判断给定值是否在集合中作为键存在
boolean containsValue(Object value) 判断给定值是否在集合中作为值存在
V get(Object key) 获取键对应的值
V put(K key, V value) 插入新的键值对
V remove(Object key) 根据键移除键值对
void putAll(Map<? extends K, ? extends V> m) 拷贝给定Map的值到该Map
void clear() 清掉所有的键值对
Set<K> keySet() 获取所有键的集合
Collection<V> values() 获取所有值的集合
Set<Map.Entry<K, V>> entrySet() 获取所有键值对的集合

在JDK1.8之后新增了较多的默认方法:

default V getOrDefault(Object key, V defaultValue) 获取指定键的值的时候可指定默认值
default void forEach(BiConsumer<? super K, ? super V> action) 遍历所有的键值对
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 替换所有键值对的值
default V putIfAbsent(K key, V value) 只有在键值对不存在的时候才添加
default boolean remove(Object key, Object value) 如果存在给定的键值对,才执行移除
default boolean replace(K key, V oldValue, V newValue) 如果存在给定的键值对,才执行替换
default V replace(K key, V value) 如果存在给定的键,就执行替换操作
default V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) 如果不存在指定键,那么就插入接口计算后的值
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
如果存在指定键,并且通过接口计算后的值不为null,就执行插入操作;为null,就移除该键
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
如果存在指定键,并且通过接口计算后的值不为null,就执行插入操作;为null存在指定键,就移除,否则不做操作
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction)
由调用者决定采用哪个值插入

注:1.8中新增的默认方法大多是对我们通常写的代码的封装,比如说如下代码:

Map<String,String> map = new HashMap<>();
if (map.get("a") == null){
    map.put("a","test");
}

如果Map中不存在,才执行添加操作。在JDK1.8封装为方法putIfAbsent(),实现就是这样的:

Map<String,String> map = new HashMap<>();
map.putIfAbsent("a", "test");

小结,Map定义了一种一一映射的数据存储方式,其中通过put添加、remove移除。(再次申明:Map和Collection没有必然联系,它们都是Java集合框架中的顶级类)。

上面提到,Map是存储的是一一对应的键值对。这个键值对,在Map中是怎么样存在的呢?


Entry

存储键值对的实体。(定义在Map中的内部接口)

定义:

interface Entry<K,V>

可以发现定义的泛型<K,V>和Map的泛型是一致的,但是值得注意的是,在接口定义这一层,他们是属于各自的泛型申明,没有任何关系。

定义了如下方法:

K getKey() 获取键值对的键
V getValue() 获取键值对的值
V setValue(V value) 设置键值对的值
JDK1.8之后提供以下static方法

都是快速获得比较器的方法)

comparingByKey() 返回以键作为比较的比较器(调用键的compareTo)
comparingByValue() 返回以值作为比较的比较器(调用值的compareTo)
comparingByKey(Comparator<? super K> cmp) 返回以键作为比较的比较器(使用传入的比较器比较)
comparingByValue(Comparator<? super V> cmp) 返回以值作为比较的比较器(使用传入的比较器比较)

小结,Entry定义了在Map中存储的最小单元数据的形式。


AbstractMap

先来看定义:

public abstract class AbstractMap<K,V> implements Map<K,V>

该抽象类实现了Map接口,按照AbstractCollection(传送门)的思路,应该也会提供一些默认的实现。

仔细看了一下源码,大部分默认实现思想和AbstractCollection基本类似,这里就只分析一下比较重要或者有差别的了。

1、和AbstractCollection一样,没有提供默认添加单个元素的具体实现(都是简单的抛出了一个异常)

public V put(K key, V value) {
    throw new UnsupportedOperationException();
}

2、在介绍Map的时候提到,Map能够提供3中基本的集合,在代码中提供了这两种基本集合的定义:

transient Set<K>        keySet;
transient Collection<V> values;

注:transient意味着该变量反序列化

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new AbstractSet<K>() {
            //...
        };
        keySet = ks;
    }
    return ks;
}

public Collection<V> values() {
    Collection<V> vals = values;
    if (vals == null) {
        vals = new AbstractCollection<V>() {
            //...
        };
        values = vals;
    }
    return vals;
}

而对于键值对的集合,则没有默认实现(每个子类实现键值对的真实存储方式可能都是有区别的)

public abstract Set<Entry<K,V>> entrySet();

3、提供了两张实现键值对存储的范例:

基本的键值对存储,每个键值对生成之后,可以重设值(val)

public static class SimpleEntry<K,V>
    implements Entry<K,V>

基本的键值对存储,每个键值对生成之后,不可以重设值(val)

public static class SimpleImmutableEntry<K,V>
    implements Entry<K,V>

具体就不分析了,就是实现了所有Entry定义的方法。

HashMap

HashTable

TreeMap

EnumMap


总结

HashMap使用哈希映射提供了快速存储键值对的方式,但线程不安全;

数据结构:数组

默认容量:16(容量要求为2的幂)

默认负载因子:0.75

扰动函数:hash ^ (hash >>> 16)

散列函数:hash & (length – 1)

外挂数据结构:链表或红黑树

最坏时间复杂度:O(N)——发生很多碰撞

最优时间复杂度:O(1)——分散均匀,没有碰撞

线程安全的实现(ConcurrentHashMap)

保存元素加入顺序的实现(LinkedHashMap)


HashTable使用哈希映射提供了不存放Null且线程安全的集合;

数据结构:数组

默认容量:11(最好为质数,这样可以均匀散列)

默认负载因子:0.75

散列函数: (hash & 0x7FFFFFFF) % tab.length

外挂数据结构:链表

最坏时间复杂度:O(N)——发生很多碰撞

最优时间复杂度:O(1)——分散均匀,没有碰撞

tip:线程安全且速度要求高,建议使用ConcurrentHashMap


TreeMap使用红黑树提供了元素有序(排序)的集合;

数据结构:红黑树

最坏时间复杂度:O(lgN)


EnumMap使用枚举的特性提供存储键为枚举的集合;

数据结构:数组

默认容量:枚举的域大小

时间复杂度:O(1)

Java集合(3)——Set

写在开始

作为我们常使用的集合之一,本章会讲解常用的HashSet、TreeSet、EnumSet,以及它们的父类、接口。

Java集合的结构图

Set

一种存放不重复元素的集合。

其结构图如下:

注:关于AbstractCollection(传送门

public interface Set<E> extends Collection<E>

代码层次可以发现,Set继承自集合Collection (传送门)。

查看方法可以发现,Set接口并没有新增任何方法,也就是 它只定义了一个不可以添加重复元素的集合类别

AbstractSet

定义了实现Set的基本框架,同时提供一些基本的代码实现。(没有新增方法)

定义如下:

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>

提供了默认实现的方法如下:

1、Set的equals方法

public boolean equals(Object o) {
    if (o == this)
        return true;

    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

2、移除给定集合所有元素的方法

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

3、哈希值的计算函数

public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}

HashSet

使用Hash映射存储(不重复)元素的集合

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>

这里有个小问题,为什么AbstractSet已经实现了Set,而HashSet还要实现Set接口?

其实这个为了代码可读性,查看源码的时候不需要多次跳转就知道其最上层的抽象类型;

很便捷的体现出,这个类就是一个Set;

多继承一次也并没有什么损失。

具体参考这里:https://stackoverflow.com/questions/4387419/why-does-arraylist-have-implements-list


查看源码,发现——内部存储是使用HashMap来存储的

private transient HashMap<E,Object> map;//反序列化

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();//占位用到的空对象

public HashSet() {
    map = new HashMap<>();
}

其中利用HashMap中key的唯一性,保证了Set里面不会有重复的元素(如果遇到两个hashcode一致的对象,但是实际上不一致的对象。这时代码没有做处理。所以在使用HashSet的时候,如果E为自定义对象,一定要处理好其hash函数)。

值得注意的是,通过以下构造,我们也能够快速构造一个有序的HashSet.

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

其中的具体实现就不分析了,因为都是调用的Map的实现。

TreeSet

使用红黑树存储(不重复)元素的集合

从Set的结构图我们可以知道,TreeSet可以向上追溯到NavigableSet和SortedSet。

为什么TreeSet要特殊一些,额外实现了这两个接口?

首先,为什么要定义这两个接口?

1、SortedSet

定义了一个不包含重复元素,且有序的集合。

新增如下函数:

Comparator<? super E> comparator() 返回一个对Set元素排序的比较器
SortedSet<E> subSet(E fromElement, E toElement) 返回一个子Set,范围是[fromElement,toElement)
SortedSet<E> headSet(E toElement) 返回一个子Set,范围是[head,toElement)
SortedSet<E> tailSet(E fromElement) 返回一个子Set,范围是[fromElement,end)
E first() 返回第一个元素
E last() 返回最后一个元素

  • Set中的顺序默认按照元素的自然顺序排列,这时获取比较器会返回null
  • 在获取子Set的时候,返回的都是半开区间。如果想要获取闭区间并且存储的类型运行计算给定值的后继值,那么只需要获取lowEndpoint 到 successor(highEndpoint) 的子区间。举个栗子(假设 s 是一个字符串有序 set):

SortedSet<String> sub = s.subSet(low, high+”\0″);——获取到一个闭区间

SortedSet<String> sub = s.subSet(low+”\0″, high);——获取到一个开区间


2、NavigableSet

在SortedSet的基础上,新增了在目标最近寻找符合条件的元素的方法。

新增如下函数:

E lower(E e) 获取小于给定元素的最大元素
E floor(E e) 获取小于等于给定元素的最大元素
E ceiling(E e) 获取大于等于给定元素的最小元素
E higher(E e) 获取大于给定元素的最小元素
E pollFirst() 返回第一个元素并移除
E pollLast() 返回最后一个元素并移除
NavigableSet<E> descendingSet() 以降序返回Set
Iterator<E> descendingIterator() 以降序返回Set 的迭代器。
NavigableSet<E> subSet(E fromElement, boolean

fromInclusive,E toElement, boolean toInclusive)

获取子Set时,严格指明是否开闭区间
NavigableSet<E> headSet(E toElement, boolean inclusive) 获取小于toElement的Set,严格指明是否开闭区间
NavigableSet<E> tailSet(E fromElement, boolean inclusive) 获取大于fromElement的Set,严格指明是否开闭区间

3、为什么要定义它们

SortedSet定义了一个有序的集合;而NavigableSet扩展了方法,并定义了一种可以快速查找的集合,这也正是TreeSet所期望的。

其次,TreeSet的实现是怎样的?

定义:

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>

和HashSet一样,内部采用了Map作为内部存储工具。

private transient NavigableMap<E,Object> m;

private static final Object PRESENT = new Object();

public TreeSet() {
    this(new TreeMap<E,Object>());
}

其他的实现也均是通过TreeMap实现的,文末有Map的传送门,这里就不具体分析了。

EnumSet

定义:

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>

JDK的部分介绍文本:

* A specialized {@link Set} implementation for use with enum types.  All of
* the elements in an enum set must come from a single enum type that is
* specified, explicitly or implicitly, when the set is created.  Enum sets
* are represented internally as bit vectors.  This representation is
* extremely compact and efficient. The space and time performance of this
* class should be good enough to allow its use as a high-quality, typesafe
* alternative to traditional <tt>int</tt>-based "bit flags."  Even bulk
* operations (such as <tt>containsAll</tt> and <tt>retainAll</tt>) should
* run very quickly if their argument is also an enum set.

大抵就是说这是:

专为存储(不重复)枚举类型设计的集合,通过使用Enum的某些特性使得该集合的时间效率和空间使用率都比普通的集合要高。

  • 在其内部存储的时候,该集合体现为一个位向量(即:用一个位表示一个元素的状态;用一组位表示一个集合,每个位对应一个元 素,而状态只可能有两种);
  • 该类可以良好的替代位域(《Effective Java》第32条也有提到);
  • 在进行批量操作的时候,如果参数也是EnumSet的话就会很快完成(因为内部都是位运算)。

注:EnumSet从定义可以看出是抽象类,也就是不可直接实例化,但是在其内部,提供了静态的实例化方法,分别返回RegularEnumSet和JumboEnumSet两个实现,后面会讲这两个的区别。

public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
    Enum<?>[] universe = getUniverse(elementType);
    if (universe == null)
        throw new ClassCastException(elementType + " not an enum");

    if (universe.length <= 64)
        return new RegularEnumSet<>(elementType, universe);
    else
        return new JumboEnumSet<>(elementType, universe);
}

基本属性:

final Class<E> elementType;//存储的枚举类型(用于校验)
final Enum<?>[] universe;//记录存储的枚举所有的变量

主要讲解如下两点:

1、存储为位向量

  • 位向量

用一个位表示一个元素的状态;用一组位表示一个集合,每个位对应一个元 素,而状态只可能有两种

假设我们有如下对人状态的标记:

enum PersonState {EATING, WORKING,SLEEPING}

对于任意的状态,人只能选择是或者不是该状态,这也就对应到计算机的0和1。我们可以假设1就是用户拥有该状态,0就是没有。

那么,如果人同时有多种状态,我们怎么区分呢?

建立一个位数组。而对于enum类型,变量在初始化的时候就会有一个index(且一但初始化就不变),可以通过enum.ordinal()获取到这个索引,并做为在位数组中的索引,也就能够唯一定位一种状态的位置了。

这里方便理解,建立一个长度位3的位数组,用来标识我们上面的某个人所具有的状态:

阿Q现在的状态是边吃饭边工作

在Java中一个byte有8位,一个int有32位,一个long有64位,每个基本数据类型都可以看做 位的一维数组。所以我们能使用基本数据类型表示一个集合,同时,增加或者减少数据,直接使用位运算就可以快速实现。

注:RegularEnumSet中使用的是long作为位数组;JumboEnumSet使用的是 long的数组 作为位数组。

  • RegularEnumSet——enum变量个数小于等于64

存储:

private long elements = 0L;

添加

public boolean add(E e) {
    typeCheck(e);

    long oldElements = elements;
    elements |= (1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

1L << ((Enum<?>)e).ordinal():对1向左移动索引那么多位,也就是将位数组中索引对应的位置置为1(举个例子:假设ordinal() =  3,而1的二进制为1,那么左移三位,就得到1000)。

然后通过或操作,将数组中的目标(索引所在的)位更改为1(继续上面例子:假设现在用于存储的long二进制是100100000,求或(并集)之后的结果为100101000,成功将标志位更改)。

移除

public boolean remove(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;

    long oldElements = elements;
    elements &= ~(1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

移除的时候还是先获取到索引位是多少,而后置非,再和原存储的long做与操作,将目标位更改为0;

还是上面的例子,移除索引为3的状态:

首先获取到在位数组中的表示1000,而后非——0111,100101000 & 0111最后得到100100000,移除标记位。

  • JumboEnumSet——enum变量个数大小超过64

存储

private long elements[];

添加

public boolean add(E e) {
    typeCheck(e);

    int eOrdinal = e.ordinal();
    int eWordNum = eOrdinal >>> 6;

    long oldElements = elements[eWordNum];
    elements[eWordNum] |= (1L << eOrdinal);
    boolean result = (elements[eWordNum] != oldElements);
    if (result)
        size++;
    return result;
}

因为采用的是long型的数组存储,所以在定位到是多少位之前,增加了一步——查找在long型数组中的位置;

int eWordNum = eOrdinal >>> 6;

也就是将enum的索引(index)无符号右移6位(也就是说除以2的6次方,即index/64),这样就得到在long型数组中的位置了。

注:将long理解为位的二维数组就好理解了。

移除

public boolean remove(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;
    int eOrdinal = ((Enum<?>)e).ordinal();
    int eWordNum = eOrdinal >>> 6;

    long oldElements = elements[eWordNum];
    elements[eWordNum] &= ~(1L << eOrdinal);
    boolean result = (elements[eWordNum] != oldElements);
    if (result)
        size--;
    return result;
}

2、为什么可以良好代替位域

首先,什么是位域?

private static final int EATING = 1 << 0;
private static final int WORKING = 1 << 1;
private static final int SLEEPING = 1 << 2;

public void addState(int flag){
    //...
}

在表示某些状态的时候,我们经常会想到以上代码。可以比较方便的通过或(|)运算添加标记位到某个集合中——这个就是位域(信息在存储时,并不需要占用一个完整的字节, 而只需占几个或一个二进制位),即,利用一个或者几个二进制位表示信息。

在上面代码中,很简单的实现添加:

addState(EATING | WORKING);

但是,当我们想要打印一下状态,查看已有状态的时候就比较麻烦了(打印出的就只是一个数字,即使转换为二进制也不是很直观)。

同时,我们想看一下一共有多少种状态,也比较麻烦,没有比较简单的遍历方式获取所有状态。

其次,如果使用EnumSet实现呢?

enum PersonState {EATING, WORKING,SLEEPING}

public void addState(Set set){
    //...
}

因为EnumSet都是使用位运算(和手动实现位域一样),但是避免了手动实现容易出现错误的问题。同时,内部使用long来存储,所以在性能上面也能够和手动实现相媲美。

addState(EnumSet.of(PersonState.EATING,PersonState.WORKING));

添加状态的代码也很直观,打印所有的状态或者其他操作也都比较便捷。

最后

  • Set可以说是数学中集合的一种代码抽象;
  • 大多的Set通过Map实现;
  • Set存放不重复的元素(如果存放值为null的对象也是,不允许重复),然而在限定null只能存一个是比较麻烦的(相对直接不允许存储null而言),所以建议Set在实现的时候不允许存储null。

附上Map的传送门

Java集合(2)——AbstractCollection

写在开始

从结构图中可以发现,几乎所以的集合(List、Set、Queue)实现的时候都直接或者间接继承了AbstractCollection。下面我们来看看它的战略意义。

Java集合的结构图

AbstractCollection

在集合框架中的位置:

public abstract class AbstractCollection<E> implements Collection<E>

从代码看,抽象类实现了接口Collection。这就意味着,它能够为子类提供部分方法的具体实现(代码复用),同时也不会影响到Collection定义的规范(抽象类可以不实现接口的函数)。

其中定义了如下两个抽象方法,所有非抽象子类都必须实现:

public abstract Iterator<E> iterator();

public abstract int size();

包含获取迭代器以及集合大小的方法,以下的默认实现都会用到这两个方法。

提供了如下默认实现:

1、判断集合是否为空

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

2、是否包含某个元素(使用equals比对)

public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

3、集合转为数组的方法(数组中元素顺序和存储顺序一致)

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

这个方法和以下代码等效

List<E> list = new ArrayList<E>(size());
for (E e : this)
    list.add(e);
return list.toArray();

同时,如果在遍历完了之后,发现还有元素没有加入到数组中(比如说在遍历的时候在集合中加入了元素),会调用以下方法进行扩容并生成新数组的操作。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        if (i == cap) {
            int newCap = cap + (cap >> 1) + 1;
            // overflow-conscious code
            if (newCap - MAX_ARRAY_SIZE > 0)
                newCap = hugeCapacity(cap + 1);
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = (T)it.next();
    }
    // trim if overallocated
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError
            ("Required array size too large");
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

其中可以看到,对数组最大的大小是Integer.MAX_VALUE,如果溢出的话,会直接抛出OutOfMemoryError异常。

4、添加单个元素的方法(没有默认实现,粗暴的抛个异常出来)

public boolean add(E e) {
    throw new UnsupportedOperationException();
}

因为默认是抛出异常,所以支持加入单个元素到集合是需要子类自己实现的。

5、移除某个指定元素

public boolean remove(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext()) {
            if (it.next()==null) {
                it.remove();
                return true;
            }
        }
    } else {
        while (it.hasNext()) {
            if (o.equals(it.next())) {
                it.remove();
                return true;
            }
        }
    }
    return false;
}

6、集合元素是否包含指定集合(也就是,指定集合元素是否都在集合中)

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

7、拷贝源集合的数据到该集合

public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

注意:这里最终也是调用添加单个元素,所以,如果不是实现一个空集合,都还是要实现add()去添加元素。

8、根据指定集合,对当前集合求余(移除两个集合的共有元素)

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

9、求源集合和当前集合的并集(共同有的元素)

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

10、清除所有元素

public void clear() {
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
}

最后

看了这么多默认实现,发现他们有很多相似的代码:

Iterator<E> it = iterator();
while (it.hasNext()) {
    //...
}

可见,对于遍历集合的方式依然推荐使用迭代器;

同时,为什么没有抽出一个方法来做这样相同的事情呢?

在JDK1.8的 Iterator 提供了如下方法:

default void forEachRemaining(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    while (hasNext())
        action.accept(next());
}

是的,它就是来做这个事情的(对集合当中的每个元素都执行接口action指定的操作),只是到得有点晚。

Java集合(1)——基础接口Collection、Map、Iterator

写在开始

无论是写业务代码。还是自己的奇思妙想,用Java集合相关的东西都比较多,一直没有认真分析其源码。本文主要讲解集合的上层基础接口Collection、Map、Iterator。通过这些接口,我们定义了实现集合的基本协议(规范)。

Java集合的结构图

Collection

Collection(集合)是List、Queue、Set的上层(也就是ArrayList、LinkedList、Vector、EnumSet、HashSet、TreeSet都是它派生出来的),其中定义了作为一个数据集的必须实现的功能。

首先,什么是集合?

包含一类数据的容器,并支持对数据的基本操作(增、删、查)。

其次,集合要求一些什么东西?

集合的子类要求实现以下基本方法:

int size() 返回集合拥有的数据大小
boolean isEmpty() 判断集合是否为空
boolean contains(Object o) 检测是否包含某个数据
Iterator<E> iterator() 返回一个标准的遍历器
Object[] toArray() 将数据集转换为同类型的数组
<T> T[] toArray(T[] a) 将数据集复制到指定的数组当中
boolean add(E e) 添加一个数据
boolean remove(Object o) 移除一个数据
boolean containsAll(Collection<?> c) 判断集合是否包含某个子集
boolean addAll(Collection<? extends E> c) 将某个集合的数据全部添加到数据集中
boolean removeAll(Collection<?> c) 移除数据集和给定集合的交集元素
boolean retainAll(Collection<?> c) 获取数据集和指定集合的交集
void clear() 移除所有元素
JDK1.8以后提供以下方法


default Spliterator<E> spliterator() 返回一个可以分割的元素遍历器(并行遍历)
default Stream<E> stream() 返回一个流
default Stream<E> parallelStream() 通过并行快速返回一个流
default boolean removeIf(Predicate<? super E> filter) 移除符合filter指定条件的元素

最后,为什么不是先抽象再接口,而是先接口再抽象?(个人见解)

接口定义了集合的规范形式;(行业规范,想要当集合,就得符合这个标准)

架构的体现,通过这样的架构,从ArrayList到HashSet能够较快的学习(结构一样,学习成本降低);

Map

Map提供了一种将值(数据)映射到键(某个对象)上的数据集存储方式。

注:虽然Map和Collection都是在java.util包下,但是他们并没有什么关系(可能它们都是数据集吧)。

通过键的索引(哈希映射),我们可以很快的获取到数据集上的某个元素。

1、Map提供的操作数据的几个方法

clear() 从 Map 中删除所有映射
remove(Object key) 从 Map 中删除键和关联的值
put(Object key, Object value) 将指定值与指定键相关联
clear() 从 Map 中删除所有映射
putAll(Map t) 将指定 Map 中的所有映射复制到此 map

putAll方法的存在实际上可以比自己多次put数据快一些,因为在内部实现中,putAll通常会初始化Map大小,避免了动态扩容的开销。

2、遍历元素的方法

entrySet() 返回 Map 中所包含映射的 Set 视图。Set 中的每个元素都是一个 Map.Entry 对象,可以使用 getKey() 和 getValue() 方法(还有一个 setValue() 方法)访问后者的键元素和值元素
keySet() 返回 Map 中所包含键的 Set 视图。删除 Set 中的元素还将删除 Map 中相应的映射(键和值)
values() 返回 map 中所包含值的 Collection 视图。删除 Collection 中的元素还将删除 Map 中相应的映射(键和值)

在小节末引用的文章中对使用entrySet和toArray对元素进行遍历做了比较,这里直接上结论:

如果只是为了单纯的遍历,使用entrySet然后使用Iterator遍历会快一些;如果需要获取到所有元素集(这个元素集在后面有用),这时使用toArray会快一些。
3、获取Map中元素的方法

get(Object key) 返回与指定键关联的值
containsKey(Object key) 如果 Map 包含指定键的映射,则返回 true
containsValue(Object value) 如果此 Map 将一个或多个键映射到指定值,则返回 true
isEmpty() 如果 Map 不包含键-值映射,则返回 true
size() 返回 Map 中的键-值映射的数目

通常情况下,containValue会比containKey慢(因为在内部如果是按照数组存储,那么到达key的位置通常具有快速映射的方式)。

大部分知识点来自这里:http://www.oracle.com/technetwork/cn/articles/maps1-100947-zhs.html

Iterator

针对集合的遍历器。

包含一下方法:

boolean hasNext() 迭代器是否还有其他元素
E next() 返回迭代器中的下一个元素
default void remove() 从集合中移除迭代器返回的最后一个元素
default void forEachRemaining() 为每个元素执行指定的操作

 

抽象类和接口

写在开始

老话说的好,面向对象编程以及面向接口编程。从开始学习面向对象的编程,这个两个词就一直围绕着我们写的每一句代码。OOP的三个基本特征:封装、继承、多态。其具体体现就是(抽象)类、接口。

抽象类

在我的理解中,抽象类就是:定义了一类事物。

比如说,苹果、板栗以及橘子都是水果,他们满足图示关系。

那么我们就可以定义一个抽象类叫做Fruit,他们有果肉(sarcocarp);在准备吃他们之前都需要剥皮(common method);同时他们都能够被吃掉,但是可能吃掉的形式可能不一样(abstract method)。

所以我们的抽象类Fruit可能是这样的:

public abstract class Fruit {
    protected Sarcocarp sarcocarp;

    protected void peeling(){
        //默认去皮方式
    }
    
    protected abstract void eat(); 

    protected static class Sarcocarp{
        public String type;
    }
}

通过以上代码,我们可以知道抽象类可以有这些:

  1. 通过abstract关键字标识抽象
  2. 包含所有子类可能都有的果肉——共有属性
  3. 提供默认实现的peel(剥皮)方法——实现代码复用
  4. 提供eat(吃)抽象方法,所有子类必须重写——实现多态
  5. 抽象类和其他类一样,只是可以包含实现abstract的方法

接口

上面说到抽象类定义了一类事物,而接口者定义了一种协议。

还是水果的例子。现在新增需求,需要添加一种不能吃的水果(比如:坏水果)。

这个时候我们不能再去集成Fruit去实现BadFruit了。因为,水果在之前的抽象当中认为是一定可以吃的。

这时就会遇到写代码的时候常见问题:抽象类封装过度,导致下层子类扩展困难。

那么,如果尝试将其部分功能剥离出来呢?

定义一个Eat接口,同时去掉抽象类中的eat抽象方法,代码如下:

public interface Eatable {
    void eat();
}

而之前的抽象类是这样的:

public abstract class Fruit {
    protected Sarcocarp sarcocarp;

    protected void peeling(){
        //默认去皮方式
    }

    protected static class Sarcocarp{
        public String type;
    }
}

现在,子类是否具有吃的功能,不再由抽象类决定,而是由其自身实现相关吃的协议,比较良好的符合开闭原则(对修改关闭,对扩展开放)。

如果子类还具有其他功能,也能够通过实现相应的接口(协议)达到目的。

通过以上接口具有以下特点:

  1. 使用interface标识
  2. 其中包含的方法不用指定可见性(可指定为public或者package,但是在编译之后都是public)
  3. 接口定义的是对象和对象之间交互的协议,通过遵循该协议,保证功能的统一
  4. 一个类只能继承一个类,但是可以实现多个接口
  5. 在JDK1.8之后,接口中通过关键字default也可以定义默认的实现方法,示例如下:
default void demo(){
   //默认实现
}

最后

撒子时候应该用抽象类,什么时候又该用接口?

个人见解:

当你认为在定义一类东西的时候(定义的事情有共同的属性、有一些相同的功能)——抽象类,但是不能高度封装,否则对扩展不利。

当你定义的东西有点虚无缥缈,他们之间没有什么共同属性,但是有一些相同的功能且相同功能实现有区别,这个时候就需要一个协议(接口)来约束这一些类和其他类的交互规则。

tips:在JDK1.8之后,接口通过default关键字能够提供默认的实现方法,抽象类的存在的合理性貌似更小了,毕竟协议(或者说规范)比抽象到具体更加重要。

如果有问题还请指出,谢谢。

Java内部类

写在开始

通过本文,你可以了解到什么是内部类?和静态内部类的区别?什么又是匿名内部类?

常规的内部类

首先,我们得了解,内部类是什么?

假如,我们定义一个描述包饺子步骤的类。

没有内部类 内部类实现
public class Dumplings {
    private int version = 0;
    //擀面皮
    public void rollingSkin(){
        buyFlour();
        mixedFlour();
        rolling();
    }
    private void buyFlour() {}
    private void mixedFlour() {}
    private void rolling() {}
    //和馅
    public void fillings(){
        chopStuffing();
        flavor();
        startFillings();
    }
    private void chopStuffing() {}
    private void flavor() {}
    private void startFillings() {}
    //包饺子
    public void make(){}
}
public class Dumplings {
    private int version = 1;
    private class RollingSkin{
        //擀面皮
        public void rollingSkin(){
            buyFlour();
            mixedFlour();
            rolling();
        }
        private void buyFlour() {}
        private void mixedFlour() {}
        private void rolling() {}
    }
    protected class Fillings{
        //和馅
        public void fillings(){
            chopStuffing();
            flavor();
            startFillings();
        }
        private void chopStuffing() {}
        private void flavor() {}
        private void startFillings() {}
    }
    //包饺子
    public void make(){}
}
  • 咋一看,内部类的实现代码量还增多了,也没有多大的变化。这样简单的封装在我看来有以下几个好处:

1、检查代码结构的时候,我们可以清楚的知道代码组成是什么样的;

2、维护代码的时候,不需要二次理解,就能够知道某几个函数是为了同一个功能而存在的;

3、通过封装,我们能够良好的对外部隐藏内部的实现方式(如果内部类有继承或者实现接口,就更能够体现这一点)。

  • 通过上面的示例代码,我们可以对内部类做以下几点总结:

1、内部类是定义在另一个类当中的特殊类

2、内部类可以任意使用外部类的变量(在编译阶段,会自动加入为外界的this)

3、内部类能够用private或者protected修饰(普通类只能用public或者默认为包可见的方式修饰)

4、内部类能够使用static修饰。

静态内部类

静态就意味不能引用外部的非static变量。也就是说,在默认情况下,静态内部类不会持有外部类的引用(在使用内部类的时候,如果持有外部的对象,比较容易发生内存泄漏)。

因为不能持有外部类的非static引用,所以静态内部类在某种程度上意味着,定义在外部类内部的一个独立类(也就是说如果如果属性为public,那么使用就和外部类其实无异)。

使用比较简单,假设我们需要定义一个饺子原料的bean,而也只有在描述包饺子的步骤(外部包裹类)的时候会用到。按照代码设计,bean应当作为独立类设计,但是因为业务需求,我们又不期望其他类能够访问到,这个时候使用静态的内部类就比较合适,代码如下:

public class Dumplings {
    private int version = 1;
    class RollingSkin{
        //擀面皮
        //...
    }
    class Fillings{
        //和馅
        //...
        Dumpling dumpling = new Dumpling();
    }
    //包饺子
    public void make(){}
    private static class Dumpling{
        public String skin;
        public String filling;
    }
}

匿名内部类

匿名,没有名字,也就是,这个类没有在代码中进行实际的定义。

又来假设了,现在我们需要能够有多个渠道同时包饺子,很简单,直接上多线程。

以下就是匿名和非匿名的实现:

非匿名 匿名
public class Dumplings {
    private int version = 1;
    class RollingSkin{
        //擀面皮
        //...
    }
    class Fillings{
        //和馅
        //...
        Dumpling dumpling = new Dumpling();
    }
    private MakeThread getMake(){
        return new MakeThread();
    }
    private static class Dumpling{
        public String skin;
        public String filling;
    }
    
    private static class MakeThread extends Thread{
        @Override
        public void run() {
            super.run();
            make();
        }
        //包饺子
        public void make(){}
    }
}
public class Dumplings {
    private int version = 1;
    class RollingSkin{
        //擀面皮
        //...
    }
    class Fillings{
        //和馅
        //...
        Dumpling dumpling = new Dumpling();
    }
    public Thread getMake(){
        return new Thread("make"){
            @Override
            public void run() {
                super.run();
                make();
            }
        };
    }
    private void make(){}
    private static class Dumpling{
        public String skin;
        public String filling;
    }
}

 

可以看出,其实匿名内部类使用的时候,实际上也是实现了Thread的子类,只是该类没有明确定义,且,类的定义只在方法期内有效。

使用匿名内部类的过程中,也要注意资源的释放,否则容易造成因为匿名内部类持有大量外部引用没有释放,导致内存泄漏。

数据结构——链表

  • 写在开始

本章主要介绍如何使用Java构建一个(单/双向)链表,通过本文,你可以轻松构建一个自己的链表。

  • 基础概念

  • 链表中的节点

通常链表中会包含我们想要保存的数据(data)以及指向下一级或上一级的句柄;

即:

对应代码大抵是酱紫的:

public class Node{
        Object data;//数据
        Node next;//指向下一节点的句柄(对象)
}
  • 链表执行的时间复杂度:
    • 索引: O(n)(线性结构,需要遍历)
    • 搜索: O(n)
    • 插入: O(1)(已知需要插入到什么位置的)
    • 移除: O(1)(已知需要从什么位置移除)
  • 链表基本包含以下基础操作:插入、删除、更新、查询
  • 故,在本章中链表做如下抽象:
public abstract class DataModel<E> {

    /**
     * 插入数据
     */
    public synchronized E insert(E element){
        return element;
    }

    /**
     * 移除某个数据
     */
    public synchronized boolean remove(E element){
        return false;
    }

    /**
     * 或者某个位置链表所存储的数据
     */
    public E childAt(int index){
        return null;
    }

    /**
     * 获取某个数据链表中的位置
     */
    public int indexOf(E element){
        return -1;
    }

    /**
     * 判断是否包含某个元素
     */
    public boolean contain(E element){
        return false;
    }

    /**
     * 设置某个元素的值
     */
    public synchronized E set(int index,E element){
        return element;
    }

    /**
     * 用于遍历的接口
     */
    public interface Consumer<E> {
        void node(int idx, E element);
    }

    /**
     * 对外提供快捷遍历链表的接口
     */
    public void foreach(Consumer<? super E> consumer) {

    }

    /**
     * 数据节点;包含基本的数据对象
     */
    protected static class Node<E>{

        public E element;

        public Node(E element) {
            this.element = element;
        }

        public String toString(){
            return element.toString();
        }
    }
}

 

包含了基础的操作,以及链表节点类Node。

  • 单向链表

    链表中的节点仅指向下一个节点,并且最后一个节点指向空。

  • 创建一个新的对象继承至我们刚刚定义的抽象类:

注:删除的效率理论上如果知道已知需要删除的节点,效率应该为O(1)。

本例中根据元素是需要线性查找,故效率为O(n)

public abstract class OneWay<E> extends DataModel<E> {

    protected OneWayNode last;
    protected OneWayNode first;

    ...

    static class OneWayNode<E> extends Node<E> {

        OneWayNode next;

        OneWayNode(E element, OneWayNode next) {
            super(element);
            this.next = next;
        }
    }
}
  •  添加

添加一个节点,大体可以分为以下两点:

  1. 上一级能够获取到下一级节点(上一级的next指向添加的节点);
  2. 指明添加节点的下一集节点;

代码如下(默认直接作为last的子节点):

   @Override
    public synchronized E insert(E e) {
        if (e == null) {
            return null;
        }
        OneWayNode<E> newNode = new OneWayNode<>(e, null);
        if (first == null) {
            first = newNode;
        }
        if (last != null) {
            last.next = newNode;
        }
        last = newNode;
        return e;
    }
  • 删除

删除,其实就是添加的逆向过程。还是分为两点来说:

  1. 让上一级节点指向自己(被删除节点)的下一级
  2. 移除自己对下一级节点的引用

代码如下:

   @Override
    public synchronized boolean remove(E e) {
        OneWayNode node = first;
        if (node.element.equals(e)) {
            first = first.next;
            return true;
        }
        while (node.next != null) {
            if (node.next.element.equals(e)) {
                if (node.next.equals(last)) {
                    node.next = null;
                    last = node;
                } else {
                    OneWayNode newNext = node.next.next;
                    node.next.next = null;
                    node.next = newNext;
                }
                return true;
            }
            node = node.next;
        }
        return false;
    }
  • 查询

查询有比较多的查询方式,本章中分为以下三种形式:

  1. 通过index查询存储的data
  2. 检查是否存在某个节点
  3. 查询某个元素在链表中的位置

因为链表为线性结构,故时间复杂度和数组一致为O(N)

代码如下:

   @Override
    public boolean contain(E e) {
        return node(e) == null;
    }

    @Override
    public E childAt(int index) {
        OneWayNode node = first;
        for (int i = 0; i <= index && node != null; i++) {
            node = node.next;
        }
        if (node == null) {
            return null;
        }
        return (E) node.element;
    }

    @Override
    public int indexOf(E element) {
        int index = -1;
        if (element == null){
            return index;
        }
        int cursor = -1;
        OneWayNode node = first;
        while (node != null) {
            if (node.element.equals(element)) {
                break;
            } else {
                cursor++;
            }
            node = node.next;
            index++;
        }
        if (index == cursor){
            index = -1;
        }
        return index;
    }

    /**
     * 根据元素获取到对应node
     */
    private OneWayNode node(E e) {
        if (e == null) {
            return null;
        }
        if (first == null) {
            return null;
        }
        OneWayNode nextNode = first.next;
        while (nextNode != null) {
            if (nextNode.element.equals(e)) {
                return nextNode;
            }
            nextNode = nextNode.next;
        }
        return null;
    }
  • 更新

更新可以更新指定位置的元素;也可以根据旧的元素索引,而后用新元素替换。

   @Override
    public E set(int index, E newVal) {
        int cursor = 0;
        OneWayNode node = first;
        while (node != null) {
            if (index == cursor) {
                node.element = newVal;
                return newVal;
            }
            node = node.next;
            cursor++;
        }
        return null;
    }

    public E update(E oldVal, E newVal) {
        OneWayNode node = first;
        while (node != null) {
            if (node.element.equals(oldVal)) {
                node.element = newVal;
                return newVal;
            }
            node = node.next;
        }
        return null;
    }
  • 反转单链表

反转单链表,比较常用的方法就是递归逐级反转。

利用递归,先到达最后的一个节点,然后开始反转。

代码如下:

public synchronized OneWay reverse() {
        OneWayNode oldLast = last;
        last = first;
        reverseNode(first);
        first = oldLast;
        return this;
    }

    private void reverseNode(OneWayNode head) {
        if (head == null || head.next == null) {
            return;
        }
        reverseNode(head.next);//每次传入旧的父节点
        head.next.next = head;
        head.next = null;
    }

单链表在使用过程中,如果想获取某个节点的上一节点,这个时候就比较麻烦了,需要通过递归,告知下一级节点,然后在通过比对,最后输出。

如果是双向链表就不要这样了,因为,它持有上一级节点的句柄。


  • 双向链表

双向,即每个节点持有三个句柄:

  1. 上一级节点的句柄
  2. 下一级节点的句柄
  3. 数据对象

大抵长这样:

同样,我们定义一个类,继承至我们定义的模型:

public class Doubly<E> extends DataModel<E> {

    int size = 0;
    private DoublyNode first;
    private DoublyNode last;

    ...

    static class DoublyNode<E> extends Node<E>{

        DoublyNode prev;
        DoublyNode next;

        public DoublyNode(E element, DoublyNode prev, DoublyNode next) {
            super(element);
            this.prev = prev;
            this.next = next;
        }
    }
}
  • 添加

对双链表的添加比但链表稍微复杂一些:

  1. 告知父节点next应指向插入节点
  2. 告知子节点prev应指向插入节点
  3. 插入节点的prev需指向父节点
  4. 插入节点的next需指向子节点

大抵代码如下:

   /**
     * 默认在最后插入子节点
     */
    @Override
    public synchronized E insert(E element) {
        DoublyNode oldLast = last;
        DoublyNode<E> newNode = new DoublyNode<>(element, oldLast,null);
        last = newNode;
        if (oldLast == null){
            first = newNode;
        } else {
            oldLast.next = newNode;
        }
        size++;
        return element;
    }

    /**
     * 在最前面插入子节点
     */
    public synchronized E insertBefore(E element) {
        DoublyNode oldFirst = first;
        DoublyNode<E> newNode = new DoublyNode<>(element, null, oldFirst);
        first = newNode;
        if (oldFirst == null){
            last = newNode;
        } else {
            oldFirst.prev = newNode;
        }
        size++;
        return element;
    }

    /**
     * 根据index在任意位置插入元素,可指定在之前或者之后
     */
    public synchronized E insertAt(int index,E element,boolean isBefore) {
        if (index < 0){
            return null;
        }
        if (first == null || last == null){
            return insert(element);
        }
        if (index == 0){
            return insertBefore(element);
        } else if (index == size - 1){
            return insert(element);
        }
        DoublyNode axis = nodeAt(index);
        if (axis == null){
            return null;
        }
        if (isBefore){
            DoublyNode prev = axis.prev;
            DoublyNode<E> newNode = new DoublyNode<>(element, prev, axis);
            prev.next = newNode;
            axis.prev = newNode;
        } else {
            DoublyNode next = axis.next;
            DoublyNode<E> newNode = new DoublyNode<>(element, axis, next);
            next.prev = newNode;
            axis.next = newNode;
        }
        size++;
        return element;
    }
  • 删除

删除的过程比较简单,先查询到相关节点,而后直接更改指向

   @Override
    public synchronized boolean remove(E element) {
        DoublyNode<E> node = node(element);
        if (node == null){
            return false;
        }
        DoublyNode prev = node.prev;
        DoublyNode next = node.next;
        if (prev != null){
            prev.next = next;
        } else {
            first = next;
        }

        if (next != null){
            next.prev = prev;
        } else {
            last = prev;
        }
        size--;
        return true;
    }
  • 查询

在定义类的时候我们通过size记录了大小,这样可以在下面通过位置(index)索引的时候节约时间。

先判断位置是位于链表前端还是后端。

具体代码如下:

    private DoublyNode nodeAt(int index) {
        if (index < 0 || index >= size){
            return null;
        }
        if (index < (size >> 1)){//是否在靠前的位置
            DoublyNode<E> node = first;
            for (int i = 0; i <= index; i++) {
                node = node.next;
            }
            return node;
        } else {
            DoublyNode<E> node = last;
            for (int i = size - 1; i >= index ; i++) {
                node = node.prev;
            }
            return node;
        }
    }

    private DoublyNode node(E e) {
        DoublyNode<E> node = first;
        if (e == null){
            for (int i = 0; i < size; i++) {
                if (node.element == null){
                    return node;
                }
                node = node.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (e.equals(node.element)){
                    return node;
                }
                node = node.next;
            }
        }
        return null;
    }

    @Override
    public E childAt(int index) {
        DoublyNode nodeAt = nodeAt(index);
        return nodeAt == null ? null : (E) nodeAt.element;
    }

    @Override
    public int indexOf(E element) {
        DoublyNode<E> node = first;
        if (node == null){
            return -1;
        }
        for (int i = 0; i < size; i++) {
            if (element.equals(node.element)){
                return i;
            }
            node = node.next;
        }
        return -1;
    }
  • 更新

更新和单向链表一致:

    @Override
    public synchronized E set(int index, E element) {
        DoublyNode node = nodeAt(index);
        if (node != null){
            node.element = element;
            return element;
        }
        return null;
    }
  • 总结

链表是数据结构中的入门。

它反应了数据的基本组织方式(如何保存对象、以及指向其他对象的句柄)。

它实际上反应的是两个实体之间的关系。

掌握了链表,再学习其他数据结构(树、图等)会容易很多,因为基本概念一致。

本文的代码可以在这里找到:GitHub_LinkedList