Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use the LinkedList container in Java". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn how to use the LinkedList container in Java.

1. The overall structure of LinkedList 1.1, the inheritance relationship of LinkedList

Public class LinkedList extends AbstractSequentialList implements List, Deque

LinkedList has the characteristics of AbstractSequentialList: AbstractSequentialList only supports sequential access, not random access like AbstractList

LinkedList has the characteristics of List.

LinkedList has the characteristics of Deque: Deque is a linear collection that supports inserting and removing elements at both ends.

1.2.The structure of LinkedList / the number of elements transient int size = 0 Node prev element / first element pointer transient Node first;// the structure of the last element pointer transient Node last;//Node node private static class Node {E item;// current element Node next;// next pointer Node prev;// current element last pointer Node (Node prev, E element, Node next) {this.item = element Structure of this.next = next; this.prev = prev;}} 1.2.1 Node

Characteristics of LinkedList

1.LinkedList is implemented through double linked lists.

2.LinkedList does not have the problem of insufficient capacity because it is a linked list.

3.LinkedList implements Deque, while the Deque interface defines methods to access elements on both sides of a dual-ended queue, so LinkedList can be used as a queue for FIFO (first-in, first-out), and LinkedList as a stack for LIFO (last-in, first-out).

2.1.Source code analysis 2.1.Adding elements / / adding elements public boolean add (E) {/ / default call, the method of adding elements at the tail linkLast (e); return true;} / / adding elements at the tail void linkLast (E e) {/ / record the current tail element final Node l = last / / create a new Node node. Prev is the current tail node, and next points to null final Node newNode = newNode (l, e, null); / / sets last to the new node last = newNode; / / determines whether the current tail node is null if (l = = null) / / the current tail node is null, first = newNode on the header node Else / / if the current tail node is not null, the newly created Node will be hung on the next pointer of the current last node l.next = number of newNode; / / elements + 1 size++; / / LinkedList modification record + 1 modCount++;}

The new element add () method is appended by default, and the core is to append the newly created Node node to the next pointer of the current last node, pseudo code:

Node newNode=new Node (); newNode.prev=last;last.next=newNode;last=newNode;last.next=null

AddFirst: first append

Public void addFirst (E e) {linkFirst (e);} / / append private void linkFirst (E e) {/ / record the current header element final Node f = first; / / create a new Node node final Node newNode = newNode (null, e, f); / / the header element points to the newly created node first = newNode / / determine whether the current header pointer is null if (f = = null) / / if the current header pointer is null, hang the newly created node on the last pointer last = newNode; else / / if the current header pointer is not null, then hang the newly created node to the f.prev = newNode; / / number of elements + 1 size++ on the prev pointer of the element. / / LinkedList modification record + 1 modCount++;}

The logic of the first append is basically the same as that of the tail append, pseudo code:

Node newNode=new Node (); newNode.next=first;first.prev=newNode;first=newNode;first.prev=null; (or: newNode.prev=null)

Specify the location to add the element: add (int index, E element):

Public void add (int index, E element) {/ / check whether the location to be inserted is legal checkPositionIndex (index); / / if the location to be inserted is last, call linkLast () if (index = = size) linkLast (element) directly; else / / if the location to be inserted is not the last, find and then insert linkBefore (element, node (index)) } / / find the location of the element to insert Node node (int index) {/ / assert isElementIndex (index); / / if the location to be inserted is less than half of the collection, I will look for if from scratch (index

< (size >

> 1)) {Node x = first; for (int I = 0; I

< index; i++) x = x.next; return x; } else { //如果要插入的位置大于等于集合的一半，我就从尾部开始找 Node x = last; for (int i = size - 1; i >

Index; iMurt -) x = x.colors; return x;}} / / insert the newly created element in front of the found element void linkBefore (E, Node succ) {/ / assert succ! = null; final Node pred = succ.prev; final Node newNode = newNode (pred, e, succ); succ.prev = newNode; if (pred = = null) first = newNode; else pred.next = newNode Size++; modCount++;}

LinkedList is a two-way linked list, it only records the position of the head and tail, and if we want to specify the position to insert, he will do this:

1. First traverse to find out the location of the element to be inserted, and then insert it; the search method is based on index

< (size >

> 1) judge the result and decide whether to traverse from the beginning or from the tail, which is similar to binary search (only cycle dichotomy at the first layer)

two。 Create a new Node node and insert it in front of the found element

We can see why the linked list is not suitable for random position reading and writing; its time complexity = O (nmax 2), if n is very large, we generally think that its time complexity = O (n).

Delete element / / override List's remove () public boolean remove (Object o) {if (o = = null) {/ / if you want to delete the element null element, look for the null element for (Node x = first; x! = null; x = x.next) {if (x.item = = null) {unlink (x); return true from scratch } else {/ / if the element to be deleted is not null, look for the non-null element for (Node x = first; x! = null; x = x.next) {if (o.equals (x.item)) {unlink (x); return true from scratch } return false;} / / execute delete logic, which in essence is to break the reference relationship between the modified element and the linked list E unlink (Node x) {/ / assert x! = null; / / record the value of the changed element, the actual function is to return the value final E element = x.item; / / record the next node of the current element final Node next = x.next / / record the previous node of the current element final Node prev = x.nodes; / / determine whether the x-> prev node is null, and if it is null, delete the header node if (prev = = null) {first = next;} else {/ / point the next pointer of the x-> prev node to the next node of the x node prev.next = next / / set the x-> prev pointer to null (break the reference relationship) x.prev = null;} / / determine whether the x-> next node is null, and if it is null, delete the tail node if (next = = null) {last = prev;} else {/ / point the prev pointer of the x-> next node to x-> prev next.prev = prev / / set the x-> next pointer to null (break reference relationship) x.next = null;} / / set the value of x to null x.item = null; / / set size-1 size--; / / modification record of the collection-1 modCount++; return element;}

Here we see that LinkedList overrides the remove method of List, and the whole delete logic is to look up and then delete. The time complexity is O (n). If you delete the first element, the time complexity is O (1). If you want to delete the trailing element, use removeLast ().

LinkedLis deletes the first element: removeFirst ()

LinkedLis deletes the trailing element: removeLast ()

The first team of LinkedLis: pollFirst (), characteristics of the queue

LinkedLit tail out: pollLast (), characteristics of the queue

2.3, iterator

The Iterator iterator can only iterate from beginning to end, while LinkedList is a bi-directional linked list, and it can also iterate from tail to head. JAVA provides a new iterator interface:

Public interface ListIterator extends Iterator {/ / determine whether there is a next element boolean hasNext (); / / get the next element E next (); / / determine whether there is a previous element boolean hasPrevious (); / / get the previous element E previous ();}

LinkedList implements this interface:

Private class ListItr implements ListIterator {the last time next () or previous () element private Node next;//lastReturned- > next points to the element private int nextIndex;// next element location private int expectedModCount = modCount;}

LinkedList traverses from after going to:

/ / whether there is the next element public boolean hasNext () {return nextIndex

< size;}public E next() { //检查集合的版本 checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); //lastReturned赋值上次next lastReturned = next; //next赋值为上次next->

Next next = next.next; / / position of the next element nextIndex++; return lastReturned.item;}

LinkedList traverses from back to front:

/ / determine whether public boolean hasPrevious () {return nextIndex > 0;} / / fetch data from the tail to the head public E previous () {checkForComodification (); if (! hasPrevious ()) throw new NoSuchElementException () / / next==null: traversal of the tail node (last) for the first time, or deletion of the tail node during the last traversal. / / Nexttail node null: traversal has already occurred. Just take the previous node (next.prev) lastReturned = next= (next==null)? Last: pointer to next.prev; / / traversal-1 nextIndex--; return lastReturned.item;}

The iterator deletes the element:

Public void remove () {checkForComodification (); / / lastReturned is the value to be deleted in this iteration / / lastReturned==null, the caller has not actively executed next () or previos (), and directly called remove () / / lastReturnedinvalid null, which is the value if (lastReturned==null) throw new IllegalStateException () assigned when the last next () or previos () method was executed. / / Save the next node that currently deletes the node (if traversing from tail to head, the value is always null) Node lastNext = lastReturned.next; / / Delete the current node unlink (lastReturned) / / next = = lastReturned: in the case of recursive order from tail to head, the first iteration, and the last element to be deleted, lastReturned = next = last is set in the / / previous () method, so next and lastReturned are equal to if (next = = lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++ } Thank you for your reading. the above is the content of "how to use LinkedList containers in Java". After the study of this article, I believe you have a deeper understanding of how to use LinkedList containers in Java, and the specific usage needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.