JAVA basic arrangement

LinkedList class

The chain list container is also learned by comparing the jdk source code.

1. Define node type

class Node<E>{

E item;
Node<E> next;
Node<E> prev;

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

}

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;
}

}

Analysis:

(1) the access permission of Node is private, because this is the Node class used inside the linked list.

(2) at the beginning, I didn't understand why the node's constructor should be passed in prev and next, but in fact, it is the simplest all parameter construction of the node. If I don't know, I can just pass null, and then assign a value when the node is inserted into the linked list.

2. Add a node (without index, direct tailing method)

public void add(Node<E> node){

if(first==null){//When there is no element in the list, the head and tail of the node are all empty.
    first=node;
    last=node;
    node.prev=null;
    node.next=null;
}
else {//The tail node is the precursor node of the node, which is the successor node of the tail node, updating the tail node.
    node.prev=last;
    last.next=node;
    last=node;
}
    size++;//Chain length increased.

}

The steps of adding a node (only the tail interpolation method is considered here):

1. If it is the first node, give it to both first and last, and the front and back of this node are empty.

2. If it is not the first node, first give the last node in the list to the precursor of this node, then give this node to the successor of last in the list, and then update the last node in the list to the current node.

void linkLast(E e) {

final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
    first = newNode;
else
    l.next = newNode;
size++;
modCount++;

}

(1) when inserting, the data should be passed in, and the task of encapsulating the data into nodes should be done internally (that is, to explain my doubts at the beginning, the second line of the source code encapsulates the nodes, that is, the last of the previous link list is passed in, followed by null)

(2) there is little difference in other logics.

3. Delete a node (with index)

public void delete(int index){

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

}

(no consideration of scope)

Analysis: the head and tail positions are considered separately, and the pointer points of other positions can be changed correspondingly.

E unlink(Node<E> x) {

final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;

if (prev == null) {
    first = next;
} else {
    prev.next = next;
    x.prev = null;
}

if (next == null) {
    last = prev;
} else {
    next.prev = prev;
    x.next = null;
}

x.item = null;
size--;
modCount++;
return element;

}

The logic is basically the same. In addition, there is such an operation when deleting

f.item = null;
f.next = null; // help GC

help gc.

4. Modify the data of a node

(1) traverse to find the index node

(2) just modify the item

5. Find the specified data

(1) traverse to find the index node

(2) take out item

<h3>Vector is thread safe, similar to arraylist, only with thread safety, but with low efficiency. </h3>

Tags: Java JDK

Posted on Sun, 10 Nov 2019 13:54:40 -0800 by gamerzfuse