Make writing a habit together! This is the 11th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
⭐️ ⭐️
This article introduces the single linked list of data structure and algorithm. Linked list is a data structure with continuous logical structure but discontinuous physical structure, which can be divided into single linked list and double linked list. The main body will introduce the addition and deletion of single linked list. Description code: Java.
📒 blog homepage: not seen flower smell blog homepage 🎉 welcome to pay attention to 🔎 like 👍 collect 🎉 🎉 message 📒 📆 Nuggets debut: 🌴 April 12, 2022 🌴 ✉️ Perseverance and hard work will be exchanged for poetry and distance! 💭 refer to books: 📚 “interesting learning data structure”, 📚 “data structure” 💬 refer to online programming website: 📚 niuke.com Falikou blogger’s code cloud Gitee, usually the program code written by the blogger are in it. Github of the blogger, the program code written by the ordinary blogger is in it. 🍭 author level is very limited, if you find mistakes, be sure to inform the author in time! Thank you, thank you!
😄1. Concept and classification of linked lists
😆1.1 Linked list concept
A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list. A linked list consists of a series of nodes (each element of the list is called a node) that can be dynamically generated at run time. Each node consists of two parts: a data field that stores data elements and a pointer field that stores the address of the next node.
Linked list structure includes two parts: one is the data domain, the second is the pointer domain, Java does not have the concept of Pointers, that might as well be called reference domain! Among them, the data field is used to store data, which can be basic data type or reference data type, no matter the former or the latter, in object-oriented programming are called objects; Under reference field used to store address, this address points to a linked list nodes or before a linked list, for reference domain variables can be a reference may also be two, only one reference variables, then the list for the singly linked list, there are two reference variables, a pointer to a precursor node, the other a pointer to a node, following is the list for the double linked list.
😆1.2 Linked list classification
In practice, there are many linked lists, which are mainly classified according to the following three points:
- Take the lead and not take the lead
- Cyclic and non-cyclic
- The linked list reference (pointer) field points to one and two
According to the first point, linked lists can be divided into: lead list and not lead list; According to the second point, linked lists can be divided into cyclic linked lists and non-cyclic linked lists. From the third point linked list can be divided into: single linked list and double linked list. Based on these three points, linked lists can be divided into 8 categories:
We can name the variables of this data field val, the references to the next node in the reference field next, and the references to the previous node prev.
nextPoint to thenull.
nextWith the first nodeprevPoint to thenull.
For a circular singly linked list, the next of the last node points to the first node. For a double linked list, the prev of the first node points to the last node, and the next of the last node points to the first node. , last question, take the lead and take the lead, is actually in front of the list add a node, the node data fields is meaningless, it is a reference to the domain point to the first node list, if it is a double linked list, prev point to null reference field, next to the first list node, is the equivalent of a node in the linked list, its data domain is invalid, Reference domain normal first node.
The most commonly used list is the single and double linked list without the lead and non-cyclic, this blog will introduce the implementation of the single linked list (not lead, non-cyclic) add and delete check.
😆1.3 The difference between linked lists and sequential lists
The physical structure of the sequential table is continuous, the logical structure is also continuous, its advantage is to support random access, obtain and modify a data is very convenient, the disadvantage is inconvenient to insert, delete elements, space utilization is not high, there may be a lot of space waste. The physical structure of the linked list is not continuous, the logical structure is continuous, it perfectly solves the shortcomings of the sequential list, its advantages are convenient to insert, delete elements, high space utilization, take and use, the disadvantage is not convenient access, do not support random access.
So, the advantages of sequential lists solve the disadvantages of linked lists, and the advantages of linked lists solve the disadvantages of sequential lists, each with its own advantages.
😄2. Theoretical basis of single linked list implementation
😆2.1 Single linked list structure
😊2.1.1 Node structure
class ListNode {
public int val;/ / data domain
ListNode next;// Reference field
ListNode() {}
ListNode(int val) {
this.val = val;// Initializes the list node value constructor}}Copy the code
😊2.1.2 Single-linked list structures and classes
public class SList {
public ListNode head;// header reference to the address of the first linked list node (not the header)
// add, delete, and change methods. }Copy the code
😆2.2 Add, delete, check and change list of single linked list
public class SList {
public ListNode head;
/ / head interpolation
public void addFirst(int data){}/ / stern interpolation
public void addLast(int data){}// Insert the first data node with subscript 0 at any position
public void addIndex(int index,int data){}// Check whether the key is included in the single linked list
public boolean contains(int key){}// Delete the node whose keyword is key for the first time
public void remove(int key){}// Delete all nodes whose value is key
public void removeAllKey(int key){}// Get the length of the single list
public int size(a){}// Prints linked list data
public void display(a){}// List destruction
public void clear(a){}}Copy the code😄3. Single linked lists from theory to practice
😆3.1 Insertion of singly linked list data
😊 3.1.1 interpolation
Insert data in front of the first node, linking the next node and pointing the header reference to itnode.
If the list is empty, direct the header reference to node.
/ / head interpolation
public void addFirst(int data){
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
}
node.next = this.head;
this.head = node;
}
Copy the code😊 3.1.2 interpolation
We go through the list to find the last node, and then we insert the new node after the last node.
If the list is empty, make the header reference point to the new node.
/ / stern interpolation
public void addLast(int data){
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
}
ListNode cur = this.head;
while(cur.next ! =null) {
cur = cur.next;
}
cur.next = node;
}
Copy the code😊3.1.3 Insert in any position
Might as well put it in number oneposInsert after node, if insert positionposfor0, using the head insertion method, if inserted after the last node, namelypos= the length of the linked list, using the tail insertion method, if other places to insert, first point to the new node to point to the firstpos+1Zero node, and then zero nodeposTwo nodes point to the new node.
If the list is empty, make the header reference point to the new node.
// Insert the first data node with subscript 0 at any position
public void addIndex(int index,int data){
if (index < 0 || index > size()) {
System.out.println("Insert position illegal!");
return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode prev = this.head;
while (index - 1! =0) {
prev = prev.next;
index--;
}
node.next = prev.next;
prev.next = node;
}
Copy the code😆3.2 Printing of single linked lists
Iterate over the list, if next of the last node is null.
public void display(a){
ListNode cur = this.head;
while(cur ! =null) {
System.out.print(cur.val + "");
cur = cur.next;
}
System.out.println();
}
Copy the code😆3.3 Search for single linked list data
Iterate through the single-linked list to determine whether the value of the data field is equal to the target value.
// Check whether the key is included in the single linked list
public boolean contains(int key){
if (this.head == null) {
return false;
}
ListNode cur = this.head;
while(cur ! =null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
Copy the code😆3.4 Obtaining the Number of single-linked List Data
Traversal method.
// Get the length of the single list
public int size(a){
int len = 0;
ListNode cur = this.head;
while(cur ! =null) {
len++;
cur = cur.next;
}
return len;
}
Copy the code😆3.5 Delete single linked list data
😊3.5.1 Delete the first occurrence of the target value in the linked list
When a linked list node is deleted, the target node is requiredcurOne node before the target nodeprevAnd letprev.next = cur,nextCan. If the list has only one node, let the header reference point directly to itnull.
To delete the first target value in a linked list, you need to find the target node first. It’s traversal, but in traversal you have to remember the node before the target node, because the list is one-way, and if you don’t remember the previous node, you can’t delete the target node. Because only the nodes where the target value first appeared in the linked list are deleted, the program can return after finding the target value to be deleted.
There are two cases of deleting linked list data:
- The target value is at the beginning of the node, so that the header reference points directly to the next node or
null. - The target value is not at the beginning, traverses the list.
// 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 = this.head.next;
ListNode prev = this.head;
while(cur ! =null) {
if (cur.val == key) {
prev.next = cur.next;
return;
}
prev = cur;
cur = cur.next;
}
System.out.println("Target node not found!");
}
Copy the code😊3.5.2 Delete all target values in all linked lists
This is basically the same as deleting the first occurrence of the target value, except that after deleting a target value node, continue to traverse to find the deletion.
// Delete all nodes whose value is key
public void removeAllKey(int key){
if (this.head == null) {
return;
}
while (this.head.val == key) {
this.head = this.head.next;
if (this.head == null) {
return;
}
}
ListNode cur = this.head.next;
ListNode prev = this.head;
while(cur ! =null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}
else{ prev = cur; cur = cur.next; }}}Copy the code😆3.6 Destruction of singly linked lists
The destruction of the linked list requires the deletion of every node. It is advisable to save the node after the node to be deleted first, and then delete the node, and so on until all the linked list nodes are deleted.
public void clear(a){
if (this.head == null) {
return;
}
while(head ! =null) {
ListNode next = head.next;
head.next = null; head = next; }}}Copy the code😄4. Single linked list add delete check change source code
😆4.1 Single-linked list classes
class ListNode {
public int val;/ / data domain
ListNode next;// Reference field
ListNode() {}
ListNode(int val) {
this.val = val;// Initializes the list node value constructor}}public class SList {
public ListNode head;
/ / head interpolation
public void addFirst(int data){
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
}
node.next = this.head;
this.head = node;
}
/ / stern interpolation
public void addLast(int data){
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
}
ListNode cur = this.head;
while(cur.next ! =null) {
cur = cur.next;
}
cur.next = node;
}
// Insert the first data node with subscript 0 at any position
public void addIndex(int index,int data){
if (index < 0 || index > size()) {
System.out.println("Insert position illegal!");
return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode prev = this.head;
while (index - 1! =0) {
prev = prev.next;
index--;
}
node.next = prev.next;
prev.next = node;
}
// Check whether the key is included in the single linked list
public boolean contains(int key){
if (this.head == null) {
return false;
}
ListNode cur = this.head;
while(cur ! =null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
// 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 = this.head.next;
ListNode prev = this.head;
while(cur ! =null) {
if (cur.val == key) {
prev.next = cur.next;
return;
}
prev = cur;
cur = cur.next;
}
System.out.println("Target node not found!");
}
// Delete all nodes whose value is key
public void removeAllKey(int key){
if (this.head == null) {
return;
}
while (this.head.val == key) {
this.head = this.head.next;
if (this.head == null) {
return;
}
}
ListNode cur = this.head.next;
ListNode prev = this.head;
while(cur ! =null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}
else{ prev = cur; cur = cur.next; }}}// Get the length of the single list
public int size(a){
int len = 0;
ListNode cur = this.head;
while(cur ! =null) {
len++;
cur = cur.next;
}
return len;
}
public void display(a){
ListNode cur = this.head;
while(cur ! =null) {
System.out.print(cur.val + "");
cur = cur.next;
}
System.out.println();
}
public void clear(a){
if (this.head == null) {
return;
}
while(head ! =null) {
ListNode next = head.next;
head.next = null; head = next; }}}Copy the code😆4.2 Test code
public class Test {
public static void main(String[] args) {
ListNode s1 = new ListNode(1);
ListNode s2 = new ListNode(2);
ListNode s3 = new ListNode(3);
ListNode s4 = new ListNode(4);
ListNode s5 = new ListNode(5);
s1.next = s2;
s2.next = s3;
s3.next = s4;
s4.next = s5;
SList list = new SList();
list.head = s1;
list.display();
list.addFirst(12);
list.addFirst(12);
list.addFirst(14);
list.display();
list.addLast(15);
list.addLast(15);
list.addLast(17);
list.display();
list.addIndex(0.22);
list.addIndex(12.23);
list.addIndex(2.24);
list.display();
list.remove(23);
list.remove(22);
list.remove(24);
list.display();
list.removeAllKey(12);
list.removeAllKey(17);
list.removeAllKey(15);
list.removeAllKey(14);
list.display();
System.out.println(list.contains(1));
System.out.println(list.contains(2));
System.out.println(list.contains(5));
System.out.println(list.contains(13));
System.out.println("-- -- -- -- -- -- -- -- -- -- -- --"); list.clear(); list.display(); }}Copy the code
😆4.3 Project files
Approach 1: the blogger’s code cloud Gitee, the usual program code written by the blogger are in it.
Channel 2: github of the blogger, the program code written by the ordinary blogger is in it.
Route 3: Contact me!