Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.

Implement these functions in the linked list class:

get(index): get the value of the index node in the linked list. Returns - 1 if the index is invalid.
addAtHead(val): add a node with value val before the first element of the linked list. After insertion, the new node will become the first node in the linked list.
addAtTail(val): append the node with value val to the last element of the linked list.
addAtIndex(index,val): add a node with value val before the index node in the linked list. If the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. If the index is less than 0, the node is inserted in the header.
Delete atindex (index): if the index is valid, delete the index node in the linked list.

Example:

Tips:

All val values are within [1, 1000].
The number of operations will be within [1, 1000].
Do not use the built-in LinkedList library.

Source: LeetCode

## analysis

I felt very simple when learning. I wrote down a lot of bug s myself..
Main problems:
1. How to define a node and what it contains
2. During the process of addition, deletion, query and modification, the change of size and the opening and closing of intervals
Two way linked list can be slightly modified on the basis of one-way linked list. This problem does not reflect the advantages of two-way linked list.

## Problem solving (Java)

```	//Single linked list
//First define the node with the pointer next and the content val
public class ListNode {
int val;
ListNode next;

ListNode(int val) {
this.val = val;
}
}

int size;

//Set initial value of linked list
size = 0;
}

public int get(int index) {
//Define auxiliary nodes to traverse the linked list (because the head node is fixed and cannot be moved)
if (index >= 0 && index < size) {
//Traverse to find the node location of the index
for (int i = 0; i <= index; i++) {
temp = temp.next;
}
//Returns the value of the location node
return temp.val;
} else {
return -1;
}
}

//Create a new node with a value of val
ListNode newNode = new ListNode(val);
//Note: first make the new node point to the next node of the head node, and then make the head node point to the new node
newNode.next = temp.next;
temp.next = newNode;
size++;
}

ListNode newNode = new ListNode(val);
//Traverse to find the tail of the linked list
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
size++;
}

public void addAtIndex(int index, int val) {
ListNode newNode = new ListNode(val);
//Because the node should also be placed when index=size, the right section is a closed section
if (index >= 0 && index <= size) {
//Traverse to find the position of the previous node of the index, because index=size should be considered
for (int i = 0; i < index; i++) {
temp = temp.next;
}
//Judge whether index=size
if (temp.next != null) {
newNode.next = temp.next;
}
temp.next = newNode;
size++;
}
}

public void deleteAtIndex(int index) {
if (index >= 0 && index < size) {
for (int i = 0; i < index; i++) {
temp = temp.next;
}
//Method of deleting node
temp.next = temp.next.next;
size--;
}
}
}
/**
* int param_1 = obj.get(index);
* obj.deleteAtIndex(index);
*/
```

```//Double linked list
//First define the node with the pointer next, pre and content val
public class ListNode {
int val;
ListNode next;
ListNode pre;
ListNode(int val) {
this.val = val;
}
}

int size;

//Set initial value of linked list
size = 0;
}

public int get(int index) {
//Define auxiliary nodes to traverse the linked list (because the head node is fixed and cannot be moved)
if (index >= 0 && index < size) {
//Traverse to find the node location of the index
for (int i = 0; i <= index; i++) {
temp = temp.next;
}
//Returns the value of the location node
return temp.val;
} else {
return -1;
}
}

//Create a new node with a value of val
ListNode newNode = new ListNode(val);
//Note: first make the new node point to the next node of the head node, and then make the head node point to the new node
if (temp.next != null){
temp.next.pre = newNode;
newNode.pre = temp;
}
newNode.next = temp.next;
temp.next = newNode;
size++;
}

ListNode newNode = new ListNode(val);
//Traverse to find the tail of the linked list
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.pre = temp;
size++;
}

public void addAtIndex(int index, int val) {
ListNode newNode = new ListNode(val);
//Because the node should also be placed when index=size, the right section is a closed section
if (index >= 0 && index <= size) {
//Traverse to find the position of the previous node of the index, because index=size should be considered
for (int i = 0; i < index; i++) {
temp = temp.next;
}
//Judge whether index=size
if (temp.next != null) {
temp.next.pre = newNode;
newNode.next = temp.next;
}
temp.next = newNode;
newNode.pre = temp;
size++;
}
}

public void deleteAtIndex(int index) {
if (index >= 0 && index < size) {
//Note that this is not the same as the single linked list (it can also be the same), and self deletion is used here
for (int i = 0; i <= index; i++) {
temp = temp.next;
}
//Delete node
if (temp.next != null){
temp.next.pre = temp.pre;
}
temp.pre.next = temp.next;
size--;
}
}
}

/**