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.
- 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:
- Pointer (Reference) to the next node; and the previous node in the case of a doubly linked list.
- The last node is called tail.
- 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
Returns the head node.
Returns the tail node.
Returns a Bool. True if the list is empty. False if the list has elements.
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.
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.
Singly Linked List
Doubly Linked List