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.firstReturns the head node.
list.lastReturns the tail node.
list.isEmptyReturns a Bool. True if the list is empty. False if the list has elements.
list.countReturns 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
AWESOME POST……………………….