Directory
1. Implementation of the interface
2. Doubly linked list
2.1 Rewrite the SeqList interface method
2.2 Add a node at the end of the current linked list (tail insertion)
2.3 Add a node at the head of the current linked list (head insertion)
2.4 Check whether the index is legal
2.5 Add a node at index position (any position)
2.6 Delete the index node
2.7 Delete the node of the first value element
2.8 Delete all nodes with value element
2.9 Modify the value of the index node to element
2.10 Get the value of the index node
2.11 Determine whether there is an element in the linked list
2.12 Get the position of element in the linked list
2.13 Print linked list
2.14 Get the length of the linked list and clear the linked list
3. Overall implementation of DoubleLinkedList
3.1 DoubleLinkedList class
3.2 Test class
3.3 Test results
LinkedList
The bottom layer is a doubly linked list structure
, because the linked list does not store elements in a continuous space, elements are stored in separate nodes, and then the nodes are connected by reference, so when inserting or deleting elements at any position, there is no need to move elements, which is more efficient.
1. Implementation of interface
(This interface can also be used in the previous singly linked list and dynamic array)
public interface SeqList<E> {
// tail plug
void add(E element);
// insert element at index position
void add(int index, E element);
// Delete the element at index < return the deleted value
E removeByIndex(int index);
// Delete the element with the first value element
void removeByValue(E element);
// Delete all elements with value element
void removeAllValue(E element);
// Set the element at the subscript index position to element, and return the value before replacement
E set(int index,E element);
E get(int index);
// Check if o is in it
boolean contains(E element);
int indexOf(E element);
int size();
void clear();
}
2. Doubly linked list by hand
2.1 Rewrite the SeqList interface method
Define the doubly linked list class, implement the SeqList method, rewrite the same as the String method.
(Alt + insert quick implementation method override)
package seqlist.link;
import seqlist.SeqList;
public class DoubleLinkedList<E> implements SeqList<E> {
private DoubleNode head;//head node
private DoubleNode tail;//tail node
private int size; // the number of car nodes, the number of stored elements
//The definition of the carriage class, the carriage is the internal class of the train, completely hidden from the outside
private class DoubleNode {
E val;//saved element
DoubleNode prev;
DoubleNode next;
DoubleNode(E val) {
this.val = val;
}
public DoubleNode(E val, DoubleNode prev, DoubleNode next) {
this.val = val;
this.prev = prev;
this. next = next;
}
}
public void addFrist(E val){ }
@Override
public void add(E element) { }
@Override
public void add(int index, E element) { }
@Override
public E removeByIndex(int index) { }
@Override
public void removeByValue(E element) { }
@Override
public void removeAllValue(E element) { }
@Override
public E set(int index, E element) { }
public boolean rangeCheck(int index){ }
@Override
public E get(int index) { }
@Override
public boolean contains(E element) { }
@Override
public int indexOf(E element) { }
@Override
public int size() { }
@Override
public void clear() { }
@Override
public String toString() { }
}
2.2 Add a node at the end of the current linked list (tail insertion)
(1) size++
(2) If the linked list is empty, the newly inserted node is the head node
(3) The linked list is not empty, point the next of the tail node of the current linked list to the new node, and the precursor prev of the new node points to the tail node
(4) Update when the new node is the tail node
public void add(E element) {
DoubleNode node = new DoubleNode(element);
size + + ;
if (head == null){
head = node;
} else {
node.prev = tail;
tail.next = node;
}
tail = node;
}
2.3 Add a node at the head of the current linked list (head insertion)
The header here is not an override method! (Because the previous dynamic array did not insert this statement again, so this method is not placed in the interface)
(1) size++
(2) If the tail of the linked list is empty, then the new node is the head node and the tail node
(3) The linked list is not empty, point the next of the new node to the head, and the precursor prev of the head points to the new node
(4) Update the new node as the head node head
public void addFirst(E element) {
DoubleNode node = new DoubleNode(element);
size + + ;
if(head == null){
tail = node;
} else {
node.next = head;
head.prev = node;
}
head = node;
}
2.4 Check whether the index is legal
private boolean rangeCheck(int index) {
if (index < 0 ||index >= size) {
return false;
}
return true;
}
2.5 Add node at position index (any position)
(1) Judging whether the index is legal or not, exiting if it is illegal
(2) Determine whether it is head plug or tail plug, call the corresponding method to add and exit
(3) Call the node method to find the predecessor prev of the index position node, and use prev.next as the successor node. The node method judges that the index is closer to the head and traverses from the front to the back, and if it is closer to the tail, it traverses from the back to the front, making the code more efficient
(4) Node link, connect the left area first, then the right area
(5) size++
DoubleNode node = new DoubleNode(element,prev,next);
Looking at the previous constructor, node.prev = prev, node.next = next has been set at this time
public void add(int index, E element) {
if (index < 0 || index > size){
throw new IllegalArgumentException("add index illegal");
}
if(head == null){
addFirst(element);
return;
}
if(index == size){
add(element);
return;
}
DoubleNode prev = node(index - 1);
DoubleNode next = prev. next;
DoubleNode node = new DoubleNode(element,prev,next);
// Process the left area first
prev. next = node;
// Process the right half area again
next.prev = node;
size + + ;
}
// According to the relationship between the incoming index and the middle position, decide whether to find the node from the front to the back or from the back to the front
// Tool method used internally
private DoubleNode node(int index){
if (index < (size>>1)){
DoubleNode ret = head;
for (int i = 0; i < index; i ++ ) {
ret = ret. next;
}
return ret;
} else {
DoubleNode ret = tail;
for (int i = size -1; i > index; i--) {
ret = ret.prev;
}
return ret;
}
}
2.6 Delete the index node
(1) Judging whether the index is legal or not, exiting if it is illegal
(2) Call the node method to find the node to be deleted
(3) Call the unlink(node) method to delete, connect the predecessor prev of the node to the successor next, set the prev and next of the node to null, and then size–. (When the predecessor prev is empty, node is the head node, and the new head node is set as the next node next of node; when the successor next is empty, node is the tail node, and the predecessor prev of node is set as the tail node)
(4) Return the value of the deleted node
public E removeByIndex(int index) {
if (!rangeCheck(index)){
throw new IllegalArgumentException("removeByIndex index illegal");
}
DoubleNode node = node(index);
unlink(node);
return node.val;
}
private void unlink(DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode next = node. next;
// Process the left half area first
if(prev == null){
this.head = next;
} else {
node. next = null;
prev. next = next;
}
// processing the right half area
if(next == null){
this.tail = prev;
} else {
node. next = null;
next.prev = prev;
}
size--;
}
2.7 Delete the node with the first value element
Traverse the linked list, find a node in the linked list that is equal to the element value, and call the unlink(node) method to delete
The figure here is consistent with the figure in 2.6
public void removeByValue(E element) {
DoubleNode node = head;
for (int i = 0; i < size; i ++ ) {
if (node.val.equals(element)){
unlink(node);
return;
}
node = node. next;
}
}
2.8 Delete all nodes with value element
(1) Traverse the linked list, find a node in the linked list that is equal to the element value, and call the unlink(node) method to delete
(2) How long the linked list is, it needs to be traversed several times, in case some nodes are not traversed (at this time, every time a deletion is performed, the size will be reduced by one, and direct size traversal may cause some nodes to be missed. So use length to save the initial size value)
public void removeAllValue(E element) {
DoubleNode node = head;
// Because the value of size will be modified after each unlink, but all elements will be deleted,
// To traverse all linked list nodes
int length = this. size;
for (int i = 0; i < length; i ++ ) {
DoubleNode next = node. next;
if (node. val. equals(element)) {
unlink(node);
}
node = next;
}
}
2.9 Modify the value of the index node to element
(1) Judging whether the index is legal or not, exiting if it is illegal
(2) Call the node method to find the node
(3) Save the value of the original node
(4) Modify the value of the node
(5) Return the value of the original node
public E set(int index, E element) {
if(!rangeCheck(index)){
throw new IllegalArgumentException("set index illegal");
}
DoubleNode node = node(index);
E oldVal = node.val;
node.val = element;
return oldVal;
}
2.10 Get the value of the index node
(1) Judging whether the index is legal or not, exiting if it is illegal
(2) Call the node method to find the node and return
public E get(int index) {
if (!rangeCheck(index)) {
throw new IllegalArgumentException("get index illegal!");
}
return node(index).val;
}
2.11 Determine whether an element exists in the linked list
public boolean contains(E element) {
DoubleNode node = head;
while (node. next != null){
if (node.val.equals(element)){
return true;
}
node = node. next;
}
return false;
}
2.12 Get the position of element in the linked list
public int indexOf(E element) {
DoubleNode node = head;
int i = 0;
while (node. next != null){
if (node.val.equals(element)){
return i;
}
i + + ;
node = node. next;
}
return -1;
}
2.13 Print linked list
public String toString() {
StringBuilder sb = new StringBuilder();
for(DoubleNode x = head; x != null; x = x.next){
sb.append(x.val);
sb.append("->");
if(x. next == null){
// At this point temp has reached the end node
sb.append("NULL");
}
}
return sb.toString();
}
2.14 Get the length of the linked list and clear the linked list
public int size() {
return size;
}
@Override
public void clear() {
while (head. next != null){
DoubleNode node = head. next;
head. next = null;
head.prev = null;
head = node;
}
head = null;
size = 0;
}
3. DoubleLinkedList overall implementation
3.1 DoubleLinkedList class
public class DoubleLinkedListimplements SeqList { private DoubleNode head;//head node private DoubleNode tail;//tail node private int size; // the number of car nodes, the number of stored elements //The definition of the carriage class, the carriage is the internal class of the train, completely hidden from the outside private class DoubleNode { E val;//saved element DoubleNode prev; DoubleNode next; DoubleNode(E val) { this.val = val; } public DoubleNode(E val, DoubleNode prev, DoubleNode next) { this.val = val; this.prev = prev; this. next = next; } } // w tail plug @Override public void add(E element) { DoubleNode node = new DoubleNode(element); size + + ; if (head == null){ head = node; } else { node.prev = tail; tail.next = node; } tail = node; } public void addFirst(E element) { DoubleNode node = new DoubleNode(element); size + + ; if(head == null){ tail = node; } else { node.next = head; head.prev = node; } head = node; } @Override public void add(int index, E element) { if (index < 0 || index > size){ throw new IllegalArgumentException("add index illegal"); } if(head == null){ addFirst(element); return; } if(index == size){ add(element); return; } DoubleNode prev = node(index - 1); DoubleNode next = prev. next; DoubleNode node = new DoubleNode(element,prev,next); // Process the left area first prev. next = node; // Process the right half area again next.prev = node; size + + ; } // According to the relationship between the incoming index and the middle position, decide whether to find the node from the front to the back or from the back to the front // Tool method used internally private DoubleNode node(int index){ if (index < (size>>1)){ DoubleNode ret = head; for (int i = 0; i < index; i ++ ) { ret = ret. next; } return ret; } else { DoubleNode ret = tail; for (int i = size -1; i > index; i--) { ret = ret.prev; } return ret; } } @Override public E removeByIndex(int index) { if (!rangeCheck(index)){ throw new IllegalArgumentException("removeByIndex index illegal"); } DoubleNode node = node(index); unlink(node); return node.val; } @Override public void removeByValue(E element) { DoubleNode node = head; for (int i = 0; i < size; i ++ ) { if (node.val.equals(element)){ unlink(node); return; } node = node. next; } } @Override public void removeAllValue(E element) { DoubleNode node = head; // Because the value of size will be modified after each unlink, but all elements will be deleted, // To traverse all linked list nodes int length = this. size; for (int i = 0; i < length; i ++ ) { DoubleNode next = node. next; if (node. val. equals(element)) { unlink(node); } node = next; } } private void unlink(DoubleNode node){ DoubleNode prev = node.prev; DoubleNode next = node. next; // Process the left half area first if(prev == null){ this.head = next; } else { node. next = null; prev. next = next; } // processing the right half area if(next == null){ this.tail = prev; } else { node. next = null; next.prev = prev; } size--; } private boolean rangeCheck(int index) { if (index < 0 ||index >= size) { return false; } return true; } @Override public E set(int index, E element) { if(!rangeCheck(index)){ throw new IllegalArgumentException("set index illegal"); } DoubleNode node = node(index); E oldVal = node.val; node.val = element; return oldVal; } @Override public E get(int index) { if (!rangeCheck(index)) { throw new IllegalArgumentException("get index illegal!"); } return node(index).val; } @Override public boolean contains(E element) { DoubleNode node = head; while (node. next != null){ if (node.val.equals(element)){ return true; } node = node. next; } return false; } @Override public int indexOf(E element) { DoubleNode node = head; int i = 0; while (node. next != null){ if (node.val.equals(element)){ return i; } i + + ; node = node. next; } return -1; } @Override public int size() { return size; } @Override public void clear() { while (head. next != null){ DoubleNode node = head. next; head. next = null; head.prev = null; head = node; } head = null; size = 0; } @Override public String toString() { StringBuilder sb = new StringBuilder(); for(DoubleNode x = head; x != null; x = x.next){ sb.append(x.val); sb.append("->"); if(x. next == null){ // At this point temp has reached the end node sb.append("NULL"); } } return sb.toString(); } }
3.2 Test class
public class DoubleNodeTest {
public static void main(String[] args) {
DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
list. add(1);
list. add(3);
list. add(5);
list. add(9);
list. add(3);
list. add(3);
System.out.println(list);
System.out.println("Empty linked list");
list. clear();
System.out.println(list);
list. add(6);
list. add(10);
list. add(5);
list. add(7);
list. add(10);
list. add(10);
System.out.println(list);
System.out.println("------------add test---------");
System.out.println("Add 99 from the end of the linked list, add 99999 to the head");
list. add(99);
list. addFirst(99999);
System.out.println(list.size());
System.out.println("add index is 2, element is 88");
list. add(2,88);
System.out.println(list);
System.out.println(list.size());
System.out.println("-----------delete test------------");
System.out.println("Delete index is 0");
list. removeByIndex(0);
System.out.println("Delete element is 6");
list. removeByValue(6);
System.out.println("Delete all 10");
list. removeAllValue(10);
System.out.println(list);
System.out.println("-----------other------------");
System.out.println("Check if it contains the element 10");
System.out.println(list.contains(10));
System.out.println("Modify index to 3, element to 19");
list.set(3,19);
System.out.println("Get the element whose index is 3");
System.out.println(list.get(3));
System.out.println(list);
System.out.println("Get the index whose element is 88");
System.out.println(list.indexOf(88));
System.out.println("Get the length of the linked list");
System.out.println(list.size());
System.out.println("Empty linked list");
list. clear();
System.out.println(list + "...");
}
}
3.3 Test Results
