Article directory
- 1.ArrayList
- 2.LinkedList
-
- 2.1 Construction of LinkedList
- 3. Overall code
- 4. Test the code
1.ArrayList
We know that List is an interface, and ArrayList is an implementation class of List interface.< /strong>
Because interfaces cannot be instantiated directly, we can let a class implement the interface, and then let this class instantiate a reference object comes out, then this objectacts as a reference to the object of the List interface.
for example:
List<Integer> list1=new ArrayList<Integer>();
example:
public static void main(String[] args) {<!-- -->
List<Integer> list=new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
for(int i=0;i<list.size();i + + ){<!-- -->
System.out.print(list.get(i));//Get the value of i subscript
}
System.out.println();
System.out.println(list.remove(2));
System.out.println(list.set(0,9));//The return value is the original i subscript value
System.out.println(list.contains(3));//Determine whether an element is included
}
List a=new ArrayList();
Then a has all the properties and methods of List, but does not have the unique properties and methods of ArrayList.
a can only call abstract methods in List overridden in ArrayList
If List and ArrayList have the same property c and method void func(). Then a.c calls c in List, because the properties will not be overridden. a.func() calls func() in ArrayList , because ArrayList overrides func() in List.
Explanation, before introducing LinkedList, let’s first talk about the shortcomings of ArrayList:
The bottom layer of ArrayList uses array to store elements, which is a continuous space. When ArrayList inserts or deletes elements at any position, it will involve The time complexity of moving elements is O(N), which is relatively inefficient. Therefore, ArrayList is not suitable for scenarios where there are many elements inserted or deleted at any position. Therefore, we introduced LinkedList (Headless doubly linked list).
2.LinkedList
First of all, we need to know: The bottom layer of LinkedList is a headless doubly linked list structure. LinkedList also implements the List interface.
Construction of nodes in LinkedList:
Since each node has a direct predecessor and direct successor, so any node in the doubly linked list >You can conveniently access its predecessor nodes and successor nodes.
The structure of a simple LinkedList containing 4 nodes:
LinkedListdoes not implement the RandomAccess interface, so LinkedListdoes not support random access.
LinkedList is suitable for scenarios inserted at any position.
Because the linked list does not store elements in continuous space, but stores them in nodes, and then connects the nodes through references, so when inserting or deleting elements at any position, there is no need to move the elements (time The complexity is O(1)) and the efficiency is higher.
2.1 Construction of LinkedList
A doubly linked list is composed of nodes. Let’s first look at the composition of nodes:
public class ListNode {<!-- -->
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val){<!-- -->
this.val=val;
}
}
We found that each node is composed of three parts, numeric domain, predecessor and successor.
Next let’s look at some basic operations of doubly linked lists (without puppet nodes):
The length of the linked list
public int size(){<!-- -->
ListNode cur=head;
int count=0;
while (cur!=null){<!-- -->
count + + ;
cur=cur.next;
}
return count;
}
Print linked list
public void display(){<!-- -->
ListNode cur=head;
while(cur!=null){<!-- -->
System.out.print(cur.val + " ");
cur=cur.next;
}
System.out.println();
}
Head plug
public void addHead(int data){<!-- -->
ListNode node=new ListNode(data);
//If the linked list is empty, directly set head=last=node
if(size()==0){<!-- -->
head=node;
last=node;
}
//If the linked list is not empty
else {<!-- -->
node.next=head;
head.prev=node;
head=node;
}
}
Tail plug
public void addTail(int data){<!-- -->
ListNode node=new ListNode(data);
//If the linked list is empty, directly set head=last=node
if(size()==0){<!-- -->
head=node;
last=node;
}else{<!-- -->//When the linked list is not empty
last.next=node;
node.prev=last;
last=node;
}
}
Insert element at index subscript
public void add(int index,int data){<!-- -->
ListNode node=new ListNode(data);
//First determine whether the index is legal
if(index<0||index>size()){<!-- -->
throw new IndexOutOfBoundsException("Array subscript out of bounds");
}
//If index==0, it is the head plug
if(index==0){<!-- -->
addHead(data);
} else if (index==size()) {<!-- -->//Tail insertion
addTail(data);
}else {<!-- -->
ListNode cur=head;
for(int i = 0; i<index; i + + ){<!-- -->
cur=cur.next;
}
cur.prev.next=node;
node.prev=cur.prev;
cur.prev=node;
node.next=cur;
}
}
Delete the head node
public void removeHead(){<!-- -->
//If the linked list is empty, it cannot be deleted
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}
//The linked list is not empty
else {<!-- -->
head=head.next;
}
}
Delete the tail node
public void removeTail(){<!-- -->
//The linked list is empty
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}else {<!-- -->
last=last.prev;
}
}
Delete the first node whose value is key
public void removeKey(int key){<!-- -->
ListNode cur=head;
//First determine whether the linked list is empty
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}
while (cur!=null){<!-- -->
if(cur.val==key){<!-- -->
if(cur==head){<!-- -->
head=head.next;
if(head!=null){<!-- -->
head.prev=null;
}else {<!-- -->
last=null;
}
}else {<!-- -->
if(cur.next!=null){<!-- -->
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}else {<!-- -->
cur.prev.next=cur.next;
last=last.prev;
}
}
return;
}else {<!-- -->
cur=cur.next;
}
}
}
Delete all nodes whose value is key
public void removeAll(int key){<!-- -->
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}
ListNode cur=head;
while(cur!=null){<!-- -->
if(cur.val==key){<!-- -->
if(cur==head){<!-- -->
head=head.next;
if(head!=null){<!-- -->
head.prev=null;
}else {<!-- -->
last=null;
}
}else {<!-- -->
if(cur.next!=null){<!-- -->
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}else {<!-- -->
cur.prev.next=cur.next;
last=last.prev;
}
}
cur=cur.next;
}else {<!-- -->
cur=cur.next;
}
}
}
Clear the linked list
public void clear(){<!-- -->
ListNode cur=head;
while (cur!=null){<!-- -->
ListNode curNext=cur.next;
cur.prev=null;
cur.next=null;
cur=curNext;
}
head=null;
last=null;
}
3. Overall code
public class LinkedList2 {
public ListNode head;
public ListNode last;
//Get the length of the linked list
public int size(){<!-- -->
ListNode cur=head;
int count=0;
while (cur!=null){<!-- -->
count + + ;
cur=cur.next;
}
return count;
}
//print linked list
public void display(){<!-- -->
ListNode cur=head;
while(cur!=null){<!-- -->
System.out.print(cur.val + " ");
cur=cur.next;
}
System.out.println();
}
//Head plug
public void addHead(int data){<!-- -->
ListNode node=new ListNode(data);
//If the linked list is empty, directly set head=last=node
if(size()==0){<!-- -->
head=node;
last=node;
}
//If the linked list is not empty
else {<!-- -->
node.next=head;
head.prev=node;
head=node;
}
}
//Tail insert
public void addTail(int data){<!-- -->
ListNode node=new ListNode(data);
//If the linked list is empty, directly set head=last=node
if(size()==0){<!-- -->
head=node;
last=node;
}else{<!-- -->//When the linked list is not empty
last.next=node;
node.prev=last;
last=node;
}
}
//Insert element at index subscript
public void add(int index,int data){<!-- -->
ListNode node=new ListNode(data);
//First determine whether the index is legal
if(index<0||index>size()){<!-- -->
throw new IndexOutOfBoundsException("Array subscript out of bounds");
}
//If index==0, it is the head plug
if(index==0){<!-- -->
addHead(data);
} else if (index==size()) {<!-- -->//Tail insertion
addTail(data);
}else {<!-- -->
ListNode cur=head;
for(int i = 0; i<index; i + + ){<!-- -->
cur=cur.next;
}
cur.prev.next=node;
node.prev=cur.prev;
cur.prev=node;
node.next=cur;
}
}
//Delete the head node
public void removeHead(){<!-- -->
//If the linked list is empty, it cannot be deleted
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}
//The linked list is not empty
else {<!-- -->
head=head.next;
}
}
//Delete the tail node
public void removeTail(){<!-- -->
//The linked list is empty
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}else {<!-- -->
last=last.prev;
}
}
//Delete the first node whose value is key
public void removeKey(int key){<!-- -->
ListNode cur=head;
//First determine whether the linked list is empty
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}
while (cur!=null){<!-- -->
if(cur.val==key){<!-- -->
if(cur==head){<!-- -->
head=head.next;
if(head!=null){<!-- -->
head.prev=null;
}else {<!-- -->
last=null;
}
}else {<!-- -->
if(cur.next!=null){<!-- -->
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}else {<!-- -->
cur.prev.next=cur.next;
last=last.prev;
}
}
return;
}else {<!-- -->
cur=cur.next;
}
}
}
//Delete all nodes whose value is key
public void removeAll(int key){<!-- -->
if(size()==0){<!-- -->
throw new RuntimeException("The linked list is empty and cannot be deleted");
}
ListNode cur=head;
while(cur!=null){<!-- -->
if(cur.val==key){<!-- -->
if(cur==head){<!-- -->
head=head.next;
if(head!=null){<!-- -->
head.prev=null;
}else {<!-- -->
last=null;
}
}else {<!-- -->
if(cur.next!=null){<!-- -->
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}else {<!-- -->
cur.prev.next=cur.next;
last=last.prev;
}
}
cur=cur.next;
}else {<!-- -->
cur=cur.next;
}
}
}
//Clear the doubly linked list
public void clear(){<!-- -->
ListNode cur=head;
while (cur!=null){<!-- -->
ListNode curNext=cur.next;
cur.prev=null;
cur.next=null;
cur=curNext;
}
head=null;
last=null;
}
}
4. Test code
public class Test {<!-- -->
public static void main(String[] args) {<!-- -->
LinkedList2 linkedList2=new LinkedList2();
linkedList2.addHead(1);
linkedList2.addHead(2);
linkedList2.addHead(3);
linkedList2.display();
//3 2 1
System.out.println("==================");
linkedList2.add(0,9);
linkedList2.display();
//9 3 2 1
System.out.println("==================");
linkedList2.removeHead();
linkedList2.display();
//3 2 1
System.out.println("==================");
}
}