A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

### Characteristics

- A linked list is represented by a pointer to the first node of the linked list.
- The first node is called head.
- If the linked list is empty, then value of head is nil.
- Each node in a list consists of at least two parts:
- Data
- Pointer (Reference) to the next node; and the previous node in the case of a doubly linked list.

- The last node is called tail.

### Applications

- Implementation of stacks and queues
- Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.
- Dynamic memory allocation : We use linked list of free blocks.
- Maintaining directory of names
- Performing arithmetic operations on long integers
- Manipulation of polynomials by storing constants in the node of linked list

### Structure

`list.first`

Returns the head node.

`list.last`

Returns the tail node.

`list.isEmpty`

Returns a Bool. True if the list is empty. False if the list has elements.

`list.count`

Returns a Int with the number of elements in the list.

`list.append(_ element: Element)`

Appends a node to the end of the list with the given element.

`list.remove(_ node: Node) -> Element?`

Removes the given node and returns the element.

`list.removeAll()`

Removes all the nodes from the list.

`list.index(at index: Int) -> Element?`

Returns the element at the given index.

### Advantages

- Dynamic Size
- Ease of Insertion/Deletion

### Disadvantages

- Random access is not allowed. Elements must be accessed sequentially.
- Extra memory space is required for the pointer(s) for each element.
- Not cache friendly.

## Singly Linked List

## Doubly Linked List