Learn linked list in 10 minutes!

Linked list is a non-contiguous storage structure in physical storage structure, and the logical order of data elements is realized through the order of reference links in the linked list.
The linked list is divided into whether it is the leader node, whether it has a ring, whether it is one-way or two-way
A one-way linked list without a leader and a ring: the highest appearance rate in the written test interview

Without the leading node, with the leading node, I drew a picture to illustrate

The purpose of the puppet node is to make it easier to write code.

```// 1. Realization of headless one-way non-circular linked list
//tail plugging
//Insert at any position, the first data node is subscript 0
//Find whether the keyword key is included in the singly 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 singly linked list
public int size();
public void display();
public void clear();
}
```

First of all, we need to use a class to represent the node. This node contains two parts, one part is the stored data and methods, and the other part is a reference to the next node.

```class LinkNode{
public int date;

this.date = date;
}
}
```

1. The first is the head plugging method

We need to judge two situations,
1. If the linked list is an empty linked list, head points to null at this time
2. If the current linked list is not empty, head is not null at this time

If it is the first case, just point the head reference to the newly inserted Node
If it is the second case, you need to consider the following operations

```	private LinkNode head = null;//Create a head node, with this head node, you can get the next of the remaining elements

//The case of an empty list
return;
}
return;
}
```

2. Print out the linked list for testing

Print all elements of a linked list:

```    public void display(){
System.out.print("[");
System.out.print(node.date);
if(node.next!= null){
System.out.print(",");
}
}
System.out.println("]");
}
```

3. Tail plug

1. If the linked list is an empty linked list, then just insert the node directly
2. If it is not empty, you need to find the last node, and point the next reference of the last node to node

```    public void addLast(int elem){
return;
}
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
```

4. Get the length of the singly linked list

```    public int size(){
int size = 0;
node != null;node = node.next){
size++;
}
return size;
}
```

Insert at any position, the first data node is subscript 0

5.1 Validity check, index<0 or greater than len is illegal
Divided into three cases of head plug and tail plug, middle plug
The analysis of interpolation is as follows. To insert index, you need to find index-1;

```	public void addIndex(int index , int elem){
int len = size();
if(index < 0 || index > len){
//illegal
return;
}
//plug
if(index == 0){
return;
}
//tail plug
if(index == len){
return;
}
LinkNode prev = getIndexPos(index - 1);
node.next = prev.next;
prev.next = node;
}
```

getIndexPos

```public LinkNode getIndexPos(int index){
for (int i = 0;i < index;i++){
cur = cur.next;
}
return cur;
}
```

6. Find whether the keyword key is included in the singly linked list

```    public boolean contains(int toFind) {
// Traverse the linked list directly and compare each element in turn
cur != null; cur = cur.next) {
if (cur.data == toFind) {
return true;
}
}
return false;
}
```

7. Delete the node whose keyword is key for the first time

There are three situations to consider
1. The case of an empty linked list

3. Delete the intermediate node (it is important to find the previous node)

```    public void romove(int toremove){
//empty list
return;
}
return;
}
//Delete in the middle
prev.next = prev.next.next;
}
//Find the previous position of the deleted element
if(cur.next.date == toremove){
return cur;
}
}
return null;
}
```

delete all key s

```public void romoveAllKey(int toremove){
return;
}
cur = cur.next){
if(cur.date == toremove){
romove(toremove);
}
}
}
```

test code

```public class Test {
public static void main(String[] args){
testremove();
testRemoveAllKey();
}
}
}
}
public static void testremove(){
System.out.println("test remove");
}
public static void testRemoveAllKey(){
System.out.println("test removeallKesy");
}
}

```

```class LinkNode{
public int date;

this.date = date;
}
}

//The case of an empty list
return;
}
return;
}
return;
}
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
public void display(){
System.out.print("[");
System.out.print(node.date);
if(node.next!= null){
System.out.print(",");
}
}
System.out.println("]");
}
public void addIndex(int index , int elem){
int len = size();
if(index < 0 || index > len){
//illegal
return;
}
//plug
if(index == 0){
return;
}
//tail plug
if(index == len){
return;
}
LinkNode prev = getIndexPos(index - 1);
node.next = prev.next;
prev.next = node;
}
for (int i = 0;i < index;i++){
cur = cur.next;
}
return cur;
}
public int size(){
int size = 0;
node != null;node = node.next){
size++;
}
return size;
}
public boolean contains(int key){
cur = cur.next){
if(cur.date == key){
return true;
}
}
return false;
}
public void romove(int toremove){
//empty list
return;
}
return;
}
//Delete in the middle
//        prev.next = prev.next.next;
prev.next = nodeToremove.next;
}
//Find the previous position of the deleted element
if(cur.next.date == toremove){
return cur;
}
}
return null;
}
public void romoveAllKey(int toremove){
return;
}