在开发中,常用的数组和ArrayList集合类,数组和数组集合都有一个重大的缺陷,就是从数组中间位置删除一个元素要付出很大的代价,因为在数组中处于被删除的元素之后的所有元素都要向数组前端移动,插入一个元素也是如此,数据结构--链表解决了这个问题.数组是在连续的存储位置上存放对象的引用,链表将每个对象存放在独立的结点中,每个结点都会存放序列中下一个结点的引用.在链表中删除一个元素就只需要更新被删除元素附近的结点引用链接.
示例:
public class LinkedListDemo {
public static void main(String[] args) {
List<String> list = new LinkedList<>();
list.add("A");
list.add("B");
Collection<String> collection = new LinkedList<>();
collection.add("C");
collection.add("D");
list.addAll(collection);
list.add(2,"F");//在下标为2的元素后面插入一个元素
List<String> linkList = new LinkedList<>();
linkList.add("G");
linkList.add("H");
list.addAll(3,linkList);//在下标为3的元素后面插入一个集合
Iterator iterator = list.iterator();
//删除两个元素 先调用next()方法
iterator.next();
iterator.next();
iterator.remove();
iterator.forEachRemaining(e -> System.out.println(e.toString()));
}
}
运行结果
![image]( "image")
链表和集合有个重要的区别,链表是个有序集合,LinkedList的add()方法在链表的尾部添加一个元素,但是实际开发中往往需要将元素添加到链表的中间.使用迭代器可以实现这个需求,迭代器可以得到集合中元素的位置,所以依赖位置的add()方法由迭代器负责,只有有序集合使用迭代器添加元素才有意义
例如:Set集合,无序,在迭代器Iterator中没有add方法,Java提供了一个子接口ListIterator,子接口中有add()方法,在Java之集合(一)中有介绍迭代器Iterator中的方法,下面介绍子接口ListIterator中的方法:
ListIterator
- boolean hasNext(); 遍历元素,有元素返回true
- E next(); 返回列表中的下一个元素
- boolean hasPrevious(); 反向遍历元素,若还有元素返回true
- E previous(); 返回列表中的前一个元素
- int nextIndex(); 返回将由后续调用next()返回的元素的索引。
- int previousIndex(); 返回将由后续调用previous()返回的元素的索引
- void remove(); 移除元素
- void set(E e); 替换next()或者previous()返回的上一个元素
- void add(E e); 将指定元素插入列表
1.ListIterator中的add()方法与Collection中的add()方法不同,Collection中的add()方法返回boolean类型,而ListIteratorzhon中的add()方法不返回boolean,它假定每次操作都会改变链表,在迭代器位置之前添加一个元素.
2.previous()方法与next()方法一样,返回被越过的对象,与之不同的是,返回的是前一个对象,和hasPrevious()方法一起yon用来反向遍历列表
3.set()方法用一个新元素替代调用next()或previous()返回的上一个元素
链表可以减少插入或删除元素付出的代价,但是不支持快速的随机访问,每次查找一个元素都要从列表头部开始重新搜索,LinkedList不做任何缓存元素位置的操作.
List
- int size();返回此列表中的元素数量
- boolean isEmpty();如果该列表不包含元素，则返回true。
- boolean contains(Object o);如果该列表包含指定的元素，则返回true。
- Iterator iterator();按正确的顺序返回列表中元素的迭代器。
- Object[] toArray();返回一个数组，该数组按适当的顺序(从第一个元素到最后一个元素)包含列表中的所有元素
- T[] toArray(T[] a);返回一个数组，该数组包含列表中所有元素的不正确序列(从第一个元素到最后一个元素);返回数组的运行时类型是指定数组的运行时类型。如果列表符合指定的数组，则返回其中的列表。否则，将使用指定数组的运行时类型和该列表的大小分配一个新数组
- boolean add(E e);将指定的元素追加到此列表的末尾
- boolean remove(Object o);从列表中删除指定元素的第一个出现项(如果存在)(可选操作)。如果此列表不包含元素，它没有改变
- boolean containsAll(Collection<?> c);如果此列表包含指定集合的所有元素，则返回true
- boolean addAll(Collection<? extends E> c);将指定集合中的所有元素按照指定集合的迭代器返回的顺序追加到此列表的末尾
- boolean addAll(int index, Collection<? extends E> c);将指定集合中的所有元素插入到此列表的指定位置
- boolean removeAll(Collection<?> c);从该列表中删除指定集合中包含的所有元素
- boolean retainAll(Collection<?> c);从这个列表中删除指定集合中不包含的所有元素
1.8
- default void replaceAll(UnaryOperator operator)将运算符应用于该元素的结果替换此列表中的每个元素。操作符抛出的错误或运行时异常将传递给调用者
1.8
- default void sort(Comparator<? super E> c) 根据指定的元素所引发的顺序对该列表进行排序
- void clear();从列表中删除所有元素
- boolean equals(Object o); 将指定的对象与此列表进行相等性比较。当且仅当指定的对象也是一个列表时，返回true
- int hashCode();返回列表的hash值
- E get(int index);返回指定位置的元素
- E set(int index, E element); 用指定的元素(可选操作)替换列表中指定位置的元素
- void add(int index, E element);在指定位置添加指定元素
- E remove(int index);移除指定元素
- int indexOf(Object o);返回此列表中指定元素的第一个出现项的索引，如果该列表不包含该元素，则返回-1。
- int lastIndexOf(Object o);返回此列表中指定元素的最后一次出现的索引，如果该列表不包含该元素，则返回-1
- ListIterator listIterator();返回列表中元素的列表迭代器
- ListIterator listIterator(int index);返回列表中元素的列表迭代器，从列表中的指定位置开始
- List subList(int fromIndex, int toIndex);返回列表中指定的fromIndex(包括)和toIndex(排除)之间的部分的视图
1.8
- default Spliterator spliterator() 为列表中的元素添加一个Spliterator
LinkedList
- public LinkedList() 构造一个空链表
- public LinkedList(Collection<? extends E> c) 构造一个链表,将元素添加到链表中
- public E getFirst() 返回列表第一个元素
- public E getLast()返回列表最后一个元素
- public E removeFirst()移除列表第一个元素
- public E removeLast()移除列表最后一个元素
- public void addFirst(E e)将元素添加到头部
- public void addLast(E e)将元素添加到尾部
- public E pollFirst()检索并删除此列表的第一个元素
- public E pollLast()检索并删除此列表的最后一个元素
- public void push(E e)将元素插入到列表的前面
- public E pop()删除并返回列表的第一个元素
- public boolean removeFirstOccurrence(Object o)删除此列表中指定元素的第一个出现项(当从头到尾遍历列表时)。如果列表不包含该元素，它将保持不变
- public boolean removeLastOccurrence(Object o)删除此列表中指定元素的最后一次出现(当从头到尾遍历列表时)。如果列表不包含该元素，它将保持不变
- public Object clone()返回此LinkedList列表的副本。(元素本身不是克隆的)
- public Object[] toArray() 返回一个数组，该数组按正确的顺序（从第一个元素到最后一个元素）包含此列表中的所有元素。
- public T[] toArray(T[] a)返回一个数组，该数组按正确的顺序（从第一个元素到最后一个元素）包含此列表中的所有元素；返回的数组的运行时类型是指定数组的运行时类型。如果列表符合指定的数组，则返回该列表。否则，将为新数组分配指定数组的运行时类型和此列表的大小。
- public Spliterator spliterator() 在该列表中的元素上创建一个延迟绑定。
- public void forEachRemaining(Consumer<? super E> action) 返回一个元素
- public boolean tryAdvance(Consumer<? super E> action) 尝试绑定,执行成功返回true
- public int characteristics() 返回Spliterator的命令或大小或尺寸
List接口用于描述一个有序集合,集合中每个元素的位置十分重要,有两种访问元素的协议,第一种是使用迭代器,第二种是用get和set方法随机访问每个元素,后者不适合用于链表,但是对数组很有用,经常用到的ArrayList类也实现了List接口,ArrayList封装了一个动态再分配的对象数组.
