Details and examples of Java Collection Framework LinkedList

Java Collection framework LinkedList in detail

LinkedList definition

package java.util;
public class LinkedList<E>
 extends AbstractSequentialList<E>
 implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
 transient int size = 0;
 transient Node<E> first;
 transient Node<E> last;
}

LinkedList overview

The & # 8195; The & # 8195; LinkedList is implemented as a bi-directional linked list, allowing duplication. (implementation of Node below) and keep the header and tail Pointers.

 private static class Node<E> {
  E item;
  Node<E> next;
  Node<E> prev;

  Node(Node<E> prev, E element, Node<E> next) {
   this.item = element;
   this.next = next;
   this.prev = prev;
  }
 }

The & # 8195; The & # 8195; There is no limit to the size of the list, but the bi-directional list itself USES more space and requires additional pointer manipulation.

The & # 8195; The & # 8195; Press the subscript to access the element-get (i)/set(i,e) to tragically traverse the linked list to move the pointer into place (if i) > One half of the array size is moved from the end.

 public E get(int index) {
  checkElementIndex(index);
  return node(index).item;
 }
 public E set(int index, E element) {
  checkElementIndex(index);
  Node<E> x = node(index);
  E oldVal = x.item;
  x.item = element;
  return oldVal;
 }

 Node<E> node(int index) {
  // assert isElementIndex(index);

  if (index < (size >> 1)) {
   Node<E> x = first;
   for (int i = 0; i < index; i++)
    x = x.next;
   return x;
  } else {
   Node<E> x = last;
   for (int i = size - 1; i > index; i--)
    x = x.prev;
   return x;
  }
 }

The & # 8195; The & # 8195; When inserting or deleting elements, it is ok to modify the pointer of the nodes before and after, but it is still necessary to traverse part of the linked list pointer to move to the position indicated by the index. Only the operation at both ends of the linked list -- add(), addFirst(),removeLast() or remove() on iterator() can avoid the pointer movement.

The & # 8195; The & # 8195; Non-thread-safe, you can call Collections.synchronizedList (new LinkedList) < > ()); The implementation.

LinkedList usage

The & # 8195; The & # 8195; Here's a quick example:

  List<Integer> list = new LinkedList<>();
  list.add(4);
  list.add(2);
  list.add(3);
  list.add(5);

  for(int i:list)
   System.out.println(i);
  System.out.println(list);

The & # 8195; The & # 8195; Operation results:

4
2
3
5
[4, 2, 3, 5]

The & # 8195; The & # 8195; LinkedList preserves the order in which data is inserted.

The use of subList

 List<Integer> list = new LinkedList<>();
  list.add(4);
  list.add(2);
  list.add(3);
  list.add(5);
  list.add(7);
  list.add(5);
  list.add(11);
  list.add(14);
  list.add(10);
  list.add(9);
  System.out.println(list);
  List<Integer> list2 = list.subList(3, 6);
  System.out.println(list2);
  list2.set(2, 50);

  System.out.println("============");
  System.out.println(list);
  System.out.println(list2);

The & # 8195; The & # 8195; Operation results:

[4, 2, 3, 5, 7, 5, 11, 14, 10, 9]
[5, 7, 5]
============
[4, 2, 3, 5, 7, 50, 11, 14, 10, 9]
[5, 7, 50]

The & # 8195; The & # 8195; Call the new list generated by the subList method in LinkedList and internally refer to the original list. If you change the value in subList, the value in the main list will also change.

Thank you for reading, I hope to help you, thank you for your support to this site!