# Link List

### What is Linked list?
A set of element bearing nodes threaded together.

- Each element is linked to its successor using a pointer
- The last element points to NULL
- Nodes are connected by pointers
- Low cost of new node
- Easy to insert or delete
- Don't need large memory reservation

### Advantages
- Can be expanded in constant time
- No predetermined size
- Space usage proportional to size
- Some manipulations more efficient than arrays
- Don't need contiguous memory

### Disadvantages
- Have to keep extra memory for pointer
- Does not have data index access
- Memory block for each node are not contiguous, need more time to access to elements.

### Why not array?
- Wastes memory space for preallocation and indices in the array that are empty.
- The size of the array is static
- Insertion may need to shift the existing elements.

### Linked List implement


## Operations
- Creating
- Access
- Traverse
- Insert node
- Remove node

## Complexity Analysis: Array vs Linked List
| Operations | Array | Linked List
| ---------------- |-------------:|-----:|
| size, is empty | O(1) | O(1) |
| get elem at rank | O(1) | O(n) |
| set elem at rank | O(1) | O(n) |
| insert element at rank| O(n) | O(1)* |
| remove element at rank| O(n) | O(1)* |
| insert first | O(n) | O(1) |
| insert last | O(1) | O(n) |

## Create
- A node is a list. element/object and next pointer = None/null
- Each addition is modifying the “next” pointer target address.
- Last node in the list is NULL, which indicates the end of the list.
- Structure built “organically” node by node, not created all at once like an array.


## Access


Two methods to access two fields:
- current.get element() returns “Banana”
- current.get next() returns “Grape”

## Traverse

- Follow the pointers.
- Display the contents of the nodes (or count) as they are traversed.
- Stop when the next pointer points to NULL.
- Time Complexity: O(n), for scanning the list of size n
- Space Complexity: O(1), for creating a temporary variable
-

## Insert

Three cases to implement insertion:

- Inserting at the head
- Inserting at the tail
- Inserting at the middle

### Insert at the head
1. Update the next pointer of new node to point to the current head.

> We set the next pointer of the new node before we
> reassign variable L.head to it

2. Update head pointer to point to the new node


### Insert at the tail
1. New nodes next pointer points to NULL.


2. Last nodes next pointer points to the new node.

> We set the next pointer for the old tail node before we
make variable tail point to the new node


### Insert at the middle
1. Move current from head to rank, set new next to current next, and current next to new node address.

- Time Complexity: O(n), since, in the worst case, we may need to insert the node at the end of the list.
- Space Complexity: O(1), for creating one temporary variable.


- Time Complexity: O(n), in the worst case, we may need to insert the node at the end of the list.
- Space Complexity: O(1), for creating one temporary variable.

## Remove
Three cases to implement removing:

- Removing at the head
- Removing at the tail
- Removing at the middle

### Remove from the head
1. Move the head to the one next to the current node.
2. Update to pointer of the previous head to NULL


### Remove from the tail
1. Unchain the last node by pointing the second last node to None/null and making it last
2. Traverse through the list and keep track of where you are with a pointer.

### Remove from the middle
1. Build two pointer, previous and current.
2. Move the current pointer to the current node.
3. Move the previous pointer to the previous node of current one.

4. Update the previous pointer to the next node of current one.

## Pointer
- Indicating the current node or element

## Traversing

Python sample code:

ite=head
while ite:
    print(ite.val)
    ite=ite.next

# Double Linked List

A Doubly Linked List contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

## Advantages
- It can trasver both forward and backward
- More efficent than the linked list when deleting the given node
- Easily insert a new node before the given node

## Disadvandages
- Extra memory needed for more pointer
- Extra steps needed when operating the node, for example, inserting a new node.