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``

``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.

• Dynamic Size
• Ease of Insertion/Deletion

• 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.

### References ### David Inga

#### Come See Me

San Francisco, CA
hello@ingax.com