Linkedlists and Queues
The structure of LinkedList
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable
Copy the codeAbstractSequentialList
Inheriting from AbstractSequentialList is essentially the same as inheriting from AbstractList. AbstractSequentialList improves methods that are not implemented in AbstractList.
Serializable
Serialization: The process of transforming an object’s state into a format that can be maintained or transferred. The opposite of serialization is deserialization, which converts a stream into an object. The Java Serializable interface is meant to tell the JVM, I’m not going to serialize this class, you’re going to serialize it for me. If we do not declare a serialVersionUID variable ourselves, the interface will generate a serialVersionUID by default. The default serialVersinUID is very sensitive to class details. Deserialization may result in an InvalidClassException (the value is recalculated each time it is serialized)
Serializable: Member variable Node is modified to transient and is serialized by overwriting the Read /writeObject methods.
Cloneable
Support for copy: implement the Cloneable interface, override the Clone method, method content default calls the clone method of the parent class.
Shallow copy
A variable of the base type is copied independently and does not change as the source variable changes
The String type is also independent after being copied
Reference types copy the address of the reference, and the variables before and after the copy refer to objects in the same heap
public Object clone(a) throws CloneNotSupportedException {
User user = (User) super.clone();
return user;
}
Copy the codeDeep copy
All reference types of variables (except String) need to implement Cloneable (arrays can be called directly), and in the Clone method, reference types need to be called separately and assigned
public Object clone(a) throws CloneNotSupportedException {
User user = (User) super.clone();
user.setName(this.name.clone());
return user;
}
Copy the code
Java pass parameters, basic type and reference type pass parameters
When Java passes parameters to a method, it copies the variables and passes them into the method body for execution. What is copied is the contents of the stack
So the basic type is the copied variable name and value, and the value changes don’t affect the source variable
The reference type copies the variable name and value (the reference address). If the object changes, the source variable will be affected (the reference address is the same).
String: is an immutable object. When reassigned, a new String is generated in the constant table (if it already exists, directly take its reference address), and the address of the new String is assigned to the new variable in the stack, so the source variable is not affected
Deque
Deque: Implements the queue interface in the Collection family, indicating that it has the capability to act as a dual-end queue.
The main difference between LinkedList and ArrayList is that LinkedList implements the Queue (Deque) interface of Collection as a dual-end Queue
2. Attributes of LinkedList
Basic attributes
The list has no length limit, and its memory address does not need to be allocated a fixed length for storage. It only needs to record the storage address of a node to complete the continuity of the whole list.
// How many nodes and elements are there
transient int size = 0;
// The first node
transient Node<E> first;
// The last node
transient Node<E> last;
//Node data structure
private static class Node<E> {
E item;// Store elements
Node<E> next;/ / the subsequent
Node<E> prev;/ / precursor
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeIn version 1.6 and before, LinkedList only held the header and tail of the queue through a header pointer. This is deep, but in terms of code readability, it makes the code more difficult to read. Therefore, in subsequent JDK updates, the head and tail nodes are distinguished. The Node class is also renamed Node.
Why is the Node class static? If you do not use static modifier, then Node is a normal inner class. In Java, a normal inner class instantiates, and by default holds a reference to the outer class, which can cause a memory leak. Using static decorates (called static inner classes), however, does not have this problem
The constructor
public LinkedList(a) {}public LinkedList(Collection<? extends E> c) {
this(a); addAll(c);// The number of operations will only be recorded once
}
Copy the codeAdd elements
public boolean add(E e) {
linkLast(e);
return true;
}
// After the target node is created, look for the precursor node. If the precursor node exists, modify the successor of the precursor node to point to the target node
void linkLast(E e) {
final Node<E> l = last;// Get the last member of the Node type inside the list object, which serves as the precursor of the newly inserted element
final Node<E> newNode = new Node<>(l, e, null);// Create a new node
last = newNode;// Make the new node the last node in the list
if (l == null)// Handle the original last node, if the list was originally an empty list
first = newNode;// Make the new node the first node
else
l.next = newNode;// If there are already elements in the list, change the list by pointing the last node to the new node
size++;// Change the size of the current list,
modCount++;// And record the number of times the list object has been modified
}
public void add(int index, E element) {
checkPositionIndex(index);// Check the subscript validity
if (index == size)// The insert position is the last, which is the logic added at the last
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
Node<E> node(int index) {
if (index < (size >> 1)) {// Start from the end where index is closer
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;// Find the element at index position
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}// The core logic of the digit addition method operates on the new node, then modifies the precursors of the original node, and finally modifies the subsequent attributes of the precursors
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;// The pred of the original position node
final Node<E> newNode = new Node<>(pred, e, succ);// Create a new node and set its precursor to the pred of the original location node, followed by the succ of the original location node
succ.prev = newNode;// Set the new node to the precursor of the original node
if (pred == null)// If the precursor is empty and the list is empty, then the new node is set to first
first = newNode;
else
pred.next = newNode;// Set the new node as the successor to the previous node
size++;// Change the size of the current list
modCount++;// Record the number of times the list object has been modified.
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
// Convert the collection to an array
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
// Get the pre-node (prev) and the last node (next)
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
// Weave the data in the collection into a linked list
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// Insert the LinkedList into the LinkedList.
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Copy the codeFinal decoration that you do not want to reassign variables at run time
LinkedList is better than ArrayList in inserting data, mainly because it only needs to change the pointer, rather than transferring the entire array of data. Because LinkedList does not implement RandomAccess, or does not support indexed search, it takes more time to find elements (n/2).
ListIterator iterator
When we use a List or Set, we often use an Iterator to traverse the List or Set. With a fallback, you don’t need to interfere with the process of its traversal, just take the data you want one at a time and process it. But there are differences in how they are used. Both lists and sets have iterator() to get their iterators. For lists, you can also get iterators from listIterator(). The two types of iterators are not always common. The main differences between iterators and Listiterators are as follows:
-
ListIterator has an add() method that adds objects to a List, while Iterator does not
-
Both ListIterator and Iterator have hasNext() and next() methods that traverse backwards, but ListIterator has hasPrevious() and previous() methods that traverse backwards (backwards). Iterator is not.
-
ListIterator can locate the current index location, as can nextIndex() and previousIndex(). Iterator does not have this capability.
-
Both can delete objects, but ListIterator can modify objects, and the set() method can. The Iierator can only traverse, not modify. Because of these features of ListIterator, you can operate on List data structures such as LinkedList. Array objects can also be implemented using iterators. Org.apache.com mons. Collections. Iterators. ArrayIterator can implement this functionality. In general, we can use Iterator, but if you need to retrieve records back and forth, you can extend your functionality with ListIterator (a bit like scrolling result sets in JDBC). A ListIterator is a bidirectional iterator. A ListIterator has no current element; its current cursor is between the element returned by a call to next() and previsous(). But there’s a problem with the following example: The following example has n+1 elements. If there are n elements, then the cursor index is 0… N plus 1. Note: The romove and set methods do not operate on the current cursor, but on the last call to next() or previous()
Remove elements
Remove from AbstractSequentialList
public E remove(int index) {
checkElementIndex(index);
//node(index) finds the element at index position
return unlink(node(index));
}
/ / remove (Object o) the method of removing elements parameters o is the data itself, rather than a LinkedList collection of elements (nodes), so need through the way of Node traversal, first find o data corresponding to the elements, and then call unlink (x) method to delete it
public boolean remove(Object o) {
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null) {
unlink(x);
return true; }}}else {
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true; }}}return false;
}
E unlink(Node<E> x) {
// Element is the data field of x
final E element = x.item;
// the next node of x
final Node<E> next = x.next;
// the last node of x
final Node<E> prev = x.prev;
If x is null, then x is the head node
if (prev == null) {
first = next;
} else {
prev.next = next;// Connect the front and back nodes of x to a bidirectional list
x.prev = null;// Set the x attribute to null
}
// If the next node of x is null, then x is the tail node
if (next == null) {
last = prev;
} else {
next.prev = prev;// Connect the front and back nodes of x to a bidirectional list
x.next = null;
}
x.item = null;// Pointing to null facilitates GC collection
size--;
modCount++;
return element;
}
Copy the code2. Remove in Deque
// Set next for the first node to the new head node, and then empty f. The removeLast operation is similar.
private E unlinkFirst(Node<E> f) {
final E element = f.item;
// Get the next node from the end node
final Node<E> next = f.next;
f.item = null;
f.next = null; Easy / / GC
// The header pointer points to the node next to the header
first = next;
// If next is null, the list has only one node
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
Copy the codeDouble ended List (Queue)
The Java implementation of queues is called LinkedList: we call LinkedList a double-ended list because it implements the Deque interface; As we know, queues are first-in, first-out, adding elements can only be added from the end of the Queue, and removing elements can only be removed from the head of the Queue. The methods in Queue embody this characteristic. Support for queued operations. Let’s take a look at some of the ways to do this:
- Pop () is a method of the stack implementation class that returns the top element of the stack and removes it
- Poll () is the data structure of the queue, getting the head element and removing the head element
- Push () is a stack implementation class method that pushes elements onto the stack
- Peek () gets the queue header element, but does not remove the queue header element
- Offer () adds the end of the queue element
As you can see, the methods provided in the Deque mainly include the above methods, so let’s take a look at how these methods are implemented in the LinkedList.
1.1. Queue Increase
Offer () adds the end of the queue element
public boolean offer(E e) {
return add(e);
}
Copy the codeThe implementation is to add an element at the end
1.2 Deleting a queue
Poll () is the data structure of the queue, getting the head element and removing the head element
public E poll(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
Copy the codeThe implementation has been described earlier, deleting the queue header element
1.3. Queue query
Peek () gets the queue header element, but does not remove the queue header element
public E peek(a) {
final Node<E> f = first;
return (f == null)?null : f.item;
}
Copy the code1.4 stack increase
Push () is a stack implementation class method that pushes elements onto the stack
The underlying implementation of the push () method is essentially calling addFirst (Object o)
public void push(E e) {
addFirst(e);
}
Copy the code1.5. Stack deletion
Pop () is a method of the stack implementation class that returns the top element of the stack and removes it
public E pop(a) {
return removeFirst();
}
public E removeFirst(a) {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
Copy the codeThree, handwritten LinkedList source code
The List interface
package com.xuchang.ds.list;
public interface List<E> {
// Return the size of the linear table
public int getSize(a);
// Check whether the linear table is null
public boolean isEmpty(a);
// Determine whether the linear table contains element o
boolean contains(E o);
// Look for the element o in the linear table, return its position index if it is found successfully; Otherwise, return -1
public int indexOf(E e);
// Get the element in the linear table at position index
public E get(int index);
// Set the index element in the linear table to e
public void set(int index, E e);
// Add element e at position index to the linear table
public void add(int index, E e);
// Delete and return the index element in the linear table
public E remove(int index);
}
Copy the codeLinkedList
package com.xuchang.ds.list;
/** * source code for LinkedList *@param <E>
*/
public class LinkedList<E> implements List<E> {
private class Node {
private E data; / / data domain
private Node next; // Point to the next Node
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
public Node(E data) {
this(data, null); }}private Node head;
private int size;
public LinkedList(a) {
head = null;
size = 0;
}
@Override
public int getSize(a) {
return size;
}
@Override
public boolean isEmpty(a) {
return size == 0;
}
@Override
public boolean contains(E o) {
Node p = head;
while(p ! =null) {
if(p.data.equals(o)){
return true;
}
p = p.next;
}
return false;
}
@Override
public int indexOf(E e) {
int result = -1;
Node p = head;
int i = 0;
while(p ! =null) {
if(p.data.equals(e)) {
result = i;
break;
}
p = p.next;
i++;
}
return result;
}
@Override
public E get(int index) {
if(index < 0 || index >= size) {
throw new IllegalArgumentException("Array index out of bounds...");
}
Node p = head;
for(int i=0; i<index; i++){
p = p.next;
}
return p.data;
}
@Override
public void set(int index, E e) {
if(index < 0 || index >= size) {
throw new IllegalArgumentException("Array index out of bounds...");
}
Node p = head;
for(int i=0; i<index; i++) {
p = p.next;
}
p.data = e;
}
@Override
public void add(int index, E e) {
if(index < 0 || index > size) {
throw new IllegalArgumentException("Data subscript out of bounds...");
}
if(index == 0) {
addFirst(e);
}else if(index == size){
addLast(e);
} else {
Node prev = head;
for(int i=0; i<index; i++) {
prev = prev.next;
}
Node node = newNode(e, prev.next); prev.next = node; size++; }}private void addFirst(E e) {
Node node = new Node(e, head);
head = node;
size++;
}
private void addLast(E e) {
Node node = new Node(e, null);
if(head == null) {
head = node;
}else {
Node prev = head;
while(prev.next ! =null) {
prev = prev.next;
}
prev.next = node;
}
size++;
}
@Override
public E remove(int index) {
if(index < 0 || index >= size) {
throw new IllegalArgumentException("Data subscript out of bounds...");
}
if(index == 0) {
return removeFirst();
}else if (index == size - 1) {
return removeLast();
}else {
Node prev = head;
for(int i=0; i<index-1; i++) {
prev = prev.next;
}
Node tmp = prev.next;
prev.next = tmp.next;
tmp.next = null;
size --;
returntmp.data; }}private E removeFirst(a) {
if(head == null) {return null;
}
E ret = head.data;
head = head.next;
size--;
return ret;
}
private E removeLast(a) {
if(head == null) {
return null;
}
E ret;
if(head.next == null) {
ret = head.data;
head = null;
}else {
Node prev = head;
while(prev.next.next ! =null) {
prev = prev.next;
}
ret = prev.next.data;
prev.next = null;
}
size--;
return ret;
}
public static void main(String[] args) {
List<Integer> list = new LinkedList<Integer>();
for(int i=0; i<10; i++) {
list.add(i, i);
}
for(int i=0; i<list.getSize(); i++) {
System.out.println("The " + i + "th element is: " + list.get(i));
}
for(int i=0; i<5; i+=2) {
list.remove(i);
}
for(int i=0; i<list.getSize(); i++) {
System.out.println("After removing, The " + i + "th element is: "+ list.get(i)); }}}Copy the code