catalogue
Classification of linked lists
Code implementation linked list
Method 2: head interpolation public void addFirst(int data)
Method 3: tail interpolation public void addLast(int data)
3. Print linked list: public void display()
5. Get the length of the single linked list: public int Size()
7. Delete the node whose keyword is key for the first time: public void remove(int key)
8. Delete all nodes with key value: public void removeAllKey(int key)
9. Clear the linked list: public void clear()
concept
Linked list: it is a discontinuous storage structure on the physical storage structure. The logical order of data elements is realized through the reference link order in the linked list
The linked list consists of a series of nodes (each element in the linked list is called a node), which can be generated dynamically at run time. Each node consists of two parts: one is the data field that stores the data element, and the other is the pointer field that stores the address of the next node. Compared with the linear table sequential structure, the operation is complex. Because it does not have to be stored in order, the complexity of the linked list can reach O(1) when inserting, which is much faster than that of another linear list sequential table, but it takes O(n) time to find a node or access a node with a specific number, and the corresponding time complexity of the linear table and the sequential table are O(logn) and O(1) respectively.
Classification of linked lists
- One way linked list
- Lead linked list, not lead linked list
- Cyclic, acyclic
After arrangement and combination, there are
That is, there are 8 kinds of linked lists, among which the one-way, no lead, acyclic and two-way, no lead and acyclic linked lists are the most important. They are also the types of linked lists introduced in this paper.
Structure of linked list
The structure of the linked list can be simulated with the following figure.
The figure shows a node of the linked list. Value is the stored data value of this node, and next is the address of the next node.
The following is a linked list of 5 nodes.
Next, let's add, delete, query and modify the linked list:
For the first node, the address is assumed to be 0x999, the stored data is 11, and the next node stores the address of the next node (assumed to be 0x888)
The address of the second node is assumed to be 0x888, the stored data is 22, and the next node stores the address of the next node (assumed to be 0x777)
The address of the third node is assumed to be 0x777, the stored data is 33, and the next node stores the address of the next node (assumed to be 0x666)
The address of the fourth node is assumed to be 0x666, the stored data is 44, and the next node stores the address of the next node (assumed to be 0x555)
For the fifth node, the address is assumed to be 0x555 and the stored data is 55. Since there is no subsequent node, the next stores a null pointer null
Define a head to store the address of the head node (the first node) (assumed to be 0x999).
Code implementation linked list
1. Create node class
The node is composed of val field (data field) and next field (pointer field). For the next field, it is a reference type and stores the address of the next node, so
Use public ListNode next to create next.
At the same time, the constructor is set to facilitate the initialization of val.
//ListNode represents a node
class ListNode{
public int val;
public ListNode next;
//Constructor
public ListNode(int a){
this.val = a;
}
}2. Create linked list
-
Method 1: enumeration method (slightly simple, slightly low)
public class MyLinkedList {
public ListNode head;//Head of linked list
public void creatList(){
ListNode listNode1 = new ListNode(11);
ListNode listNode2 = new ListNode(22);
ListNode listNode3 = new ListNode(33);
ListNode listNode4 = new ListNode(44);
ListNode listNode5 = new ListNode(55);
this.head = listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
}
}Directly assign val and initialize next.
Note: there is no need to assign a value to the next of the last node, because next is a reference type. If it is not assigned, it will be null by default.
-
Method 2: head interpolation public void addFirst(int data)
Header insertion refers to inserting a new node at the head node of the linked list, defining a node to represent the node, and then assigning a value to the next node, which can be completed by using node.next = this.head (Note: head should point to the new node)
code implementation
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}-
Method 3: tail interpolation public void addLast(int data)
Tail interpolation refers to inserting a new node at the tail node of the linked list, defining a node to represent the node, and then assigning a value to the next of the original last node. First move the head to the original last node and assign a value with head.next = node (note that if the linked list is not empty, cur needs to be defined to replace the head)
code implementation
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head == null){
this.head = node;
}else {
ListNode cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
}3. Print linked list: public void display()
Knowing the structure of the linked list, we can know that nodes are connected through next. In addition, we have created the head, that is, the address of the head node, and printed the linked list through the movement of the head.
Note: in order to make the head always exist and meaningful, we define a cur in the display() function: ListNode cur = this.head; To replace head.
For head movement, head = head.next can be used.
Code implementation:
public void display(){
ListNode cur = this.head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}4. Check whether the keyword is included and whether the key is in the single linked list: public boolean contains(int key)
To find the key, you can use the head movement to find the key (Note: also define a cur to replace the head)
code implementation
public boolean contains(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}5. Get the length of the single linked list: public int Size()
Define the counter count = 0, and judge the length of the linked list by moving the head (Note: also define a cur to replace the head)
code implementation
public int Size(){
int count = 0;
ListNode cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}6. Insert at any position. The first data node is subscript 0: public boolean addIndex(int index,int data)
For example, we insert a node with a value of 1314 and an address of 0x520 (set as node reference), that is, the value of val field is 1314, the next field is null and the address is 520, and insert the node into position 3,
After analysis, it is necessary to move the head to position 2 (Note: use cur instead of head to prevent head loss), and then
node.next = cur.next changes the next field of the node to the address of the next node, and then cur.next = node.next changes the previous node
The next field of the node is changed to the address of the node.
public void addIndex(int index,int data){
if(index < 0 ||index > Size()){ //Judge the legitimacy of index location
return;
}
if(index == 0){ //Equivalent to head insertion
addFirst(data);
return;
}
if(index = Size()){ //Equivalent to tail interpolation
addLast(data);
return;
}
ListNode cur = findIndex(index);//Find the address of the previous location of the index location
ListNode node = new ListNode(data);//Initialize node
node.next = cur.next;
cur.next = node;
}7. Delete the node whose keyword is key for the first time: public void remove(int key)
For the node that deletes the key value for the first time, if it is not the head node, we only need to change the next field of the previous node of the node corresponding to the key value to the next field of the node corresponding to the key value.
For head nodes, head directly = head.next.
For the previous node of the node corresponding to the key value, we can write a function to find it to facilitate subsequent code writing.
//Find the precursor of key (previous node)
public ListNode searchPrev(int key){
ListNode cur = this.head;
while(cur.next != null){
if(cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}
//Delete the node whose keyword is key for the first time
public void remove(int key){
if(this.head == null){
return;
}
if(this.head.val == key){
this.head = this.head.next;
return;
}
ListNode cur = searchPrev(key);
if(cur == null){
return; //There are no nodes to delete
}
ListNode del = cur.next;//Define the node to delete
cur.next = del.next;
}8. Delete all nodes with key value: public void removeAllKey(int key)
To delete all nodes with the value of key, we only need to call the remove function written above several times, but,
To meet the interview difficulty, the requirement is to traverse the linked list and delete all nodes with key value.
Case 1: the key is continuous, as follows (nodes 1, 2 and 3)
Case 2: the key is discontinuous, as follows (nodes 1 and 3)
Code implementation:
public ListNode removeAllKey(int key){
if(this.head = null){
return null;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while(cur != null){
if(cur.val == key){
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
if(this.head.val == key){
this.head = this.head.next;
}
return this.head;
}9. Clear the linked list: public void clear()
1. Simple and crude method: set the head node to null, head = null; that will do
2. Delicate and gentle approach: set each node to be empty
public void clear(){
while(this.head != null){
ListNode curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}Source code
import java.util.List;
//ListNode represents a node
class ListNode{
public int val;
public ListNode next;
//Constructor
public ListNode(int a){
this.val = a;
}
}
public class MyLinkedList {
public ListNode head;//Head of linked list
public void creatList() {
ListNode listNode1 = new ListNode(11);
ListNode listNode2 = new ListNode(22);
ListNode listNode3 = new ListNode(33);
ListNode listNode4 = new ListNode(44);
ListNode listNode5 = new ListNode(55);
this.head = listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
}
//Head insertion
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
/*if(this.head == null){
this.head = node;
}else{
node.next = this.head;
this.head = node;
}*/
}
//Tail interpolation
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
//Print sequence table
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//Find out whether the keyword is included and whether the key is in the single linked list
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//Get the length of the single linked list
public int Size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//Find the address of the previous location of the index location
public ListNode findIndex(int index) {
ListNode cur = head.next;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//Insert at any position, and the first data node is subscript 0
public void addIndex(int index, int data) {
if (index < 0 || index > Size()) {
return;
}
if (index == 0) { //Equivalent to head insertion
addFirst(data);
return;
}
if (index == Size()) { //Equivalent to tail interpolation
addLast(data);
return;
}
ListNode cur = findIndex(index);//Find the address of the previous location of the index location
ListNode node = new ListNode(data);//Initialize node
node.next = cur.next;
cur.next = node;
}
//Find the precursor of key (previous node)
public ListNode searchPrev(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//Delete the node whose keyword is key for the first time
public void remove(int key) {
if (this.head == null) {
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPrev(key);
if (cur == null) {
return; //There are no nodes to delete
}
ListNode del = cur.next;//Define the node to delete
cur.next = del.next;
}
//Delete all nodes with the value of key
public ListNode removeAllKey(int key) {
if (this.head = null) {
return null;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
if (this.head.val == key) {
this.head = this.head.next;
}
return this.head;
}
//Empty linked list
public void clear() {
while (this.head != null) {
ListNode curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
}