## WHAT
### Definition
- A **linked list** is an ordered collection of nodes where each node **stores a value and a reference to the next node**, allowing sequential access.
- 链表并不需要一整块连续的内存空间存储元素。链表的元素可以分散在内存空间的天涯海角，通过每个节点上的 `next, prev` 指针，将零散的内存块串联起来形成一个链式结构。
### Complexity Analyze
- Insert (Add) / Delete
- at the end: O (n)
- at the head: O (1)
- insert in the middle (after given node): O (1)
- insert in the middle (don't have given node): O (n)
- Access (Read)
- give an index, retrieve the value at index: O (n)
- give an index, modify the value at index: O (n)
### Type
- Singly Linked List
- Doubly Linked List
## Grammar
- the essence of linked lists
- all of the crud, we must implement them by using `next` to point the node
- we can't access an element directly by using index, and must use `.next`
### Structure Definition
- A linked list is composed of nodes connected via the `next` pointer.
- We can initialize
- Node class (ListNode)
- every node has 2 parts
- current node's value
- a reference/pointer to the next node
- LinkedList class
- How to create an empty linked list?
- set the head node to a null reference
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
```
### Create a Linked List based on a list
give you a list (eg `[1, 2, 3]`), turn it into a linked list
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def create(self, data):
if not data:
return
self.head = ListNode(data[0]) # 1. initialize the head node as [val: 3, next: None]
current = self.head # 2."current" is the head node
for i in range(1, len(data)):
current.next = ListNode(data[i]) # 3. point to the new node
current = current.next # 4.move on "current" to the next node
```
1. initialize the head node
2. assign "current" to the head node
3. loop
1. use "next" point to the new node from the head node
2. assign "current" to the new node (`current.next`)
### get the length of a linked list
```python
def length(self):
count = 0
cur = self.head
while cur: # equals to while cur is not None
count += 1
cur = cur.next
return count
```
### Read
#### Traverse
```python
def traverse(self):
cur = self.head
while cur:
print(current.val)
cur = cur.next
```
#### Search (based on value)
```python
def search(self, target):
cur = self.head
while cur:
if cur.value == target:
return True
current = current.next
ruturn False
```
#### Search (based on index)
- use index and `while` loop
```python
def get_nth_value(head, index):
cur = head
count = 0
while cur:
if count == index:
return cur.val
cur = cur.next
count += 1
return None
```
- use range
```python
def get_nth_value(head, index):
cur = head
for _ in range(n):
if cur is None:
return None
cur = cur.next
return cur.val if cur else None
```
### Insert
- 3 cases
- at head
- at tail
- in the middle
#### Insert at Head
```python
def insertFront(self, val):
node = ListNode(val)
node.next = self.head
self.head = node
```
- Time complexity is O1, because it's not affect the whole linked list, just create a new node and update the head pointer.
#### Insert at Tail
```python
def insertRear(self, val):
node = ListNode(val)
cur = self.head
while cur.next:
cur = cur.next #quickly find the last node
cur.next = node
```
- Time complexity is On, because we need to use `next` to traverse the whole linked list to find the final node, and then add the new node behind it
#### Insert in the middle
```python
def insertInside(self, index, val):
cur = self.head
for _ in range(index):
cur = cur.next # 1. find the target node based on index, and assign it to "cur"
new_node = ListNode(val) # 2. initialize a new node
new_node.next = cur.next #3. let the new node's "next" point to the next node of current node
cur.next = new_node # 4. let the current node's "next" point to the new node
```
1. use traverse to find the target node at first, we will insert the new node next to it
2. initialized a new node
3. 先把后面接上：assign `cur.next` to `new_node.next`
4. 再把前面接上：assign `new_node` to `cur.next`
- time complexity is On, because we need to traverse the linked list until the target node
### Delete
- 3 cases as well
- at head
- at tail
- in the middle
#### Delete at Head
```python
def removeFront(self):
if self.head:
self.head = self.head.next
```
- directly assign `the next node of the head ` to the head
Time complexity is O1, because it's only 1 step move
#### Delete at Tail
```python
def removeRear(self):
if not sefl.head or not self.head.next:
return
cur = head
while cur.next.next:
cur = cur.next
cur.next = None
```
- edge case check at first
- check if linked list is empty or only has 1 node
- main idea: find the second-to-last node and set the `next` pointer to `None`
- Why the `cur.next.next` can find the second-to-last node?
- while `next.next` is not `None`, cur is the third-to-last node, we implement `cur = cur.next` again means we move 1 step forward, cur became to the second-to-last node
- Time complexity: On
#### Delete in the middle
```python
def removeInside(self, index):
count = 0
cur = self.head
for _ in range(index-1):
cur = cur.next
del_node = cur.next
cur.next = del_node.next
```
- find the node in front of the node need to be deleted
- find the del_node (the next node of cur)
- assign the next node of the del_node to the `cur.next`
## Edge Case
### Dummy
## Solution Pattern
### Two Pointers
- two pointers point to nodes in a linked list
- must move in the same direction
- one fast, one slow
- 隔开距离
- 移动速度
- Recursive