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
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.
Appends a node to the end of the list with the given element.
Removes the given node and returns the element.
Removes all the nodes from the list.
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class SinglyLinkedList<Element> { | |
| private var head: SinglyLinkedListNode<Element>? | |
| private var tail: SinglyLinkedListNode<Element>? | |
| public var isEmpty: Bool { | |
| return head == nil | |
| } | |
| public var count: Int { | |
| var node = head | |
| var count = 0 | |
| while node != nil { | |
| count += 1 | |
| node = node!.next | |
| } | |
| return count | |
| } | |
| public var first: SinglyLinkedListNode<Element>? { | |
| return head | |
| } | |
| public var last: SinglyLinkedListNode<Element>? { | |
| return tail | |
| } | |
| public func append(_ element: Element) { | |
| let newNode = SinglyLinkedListNode(element) | |
| if tail != nil { | |
| tail!.next = newNode | |
| } else { | |
| head = newNode | |
| } | |
| tail = newNode | |
| } | |
| public func index(of element: Int) -> SinglyLinkedListNode<Element>? { | |
| if element < 0, head == nil { | |
| return nil | |
| } | |
| var node = head | |
| for _ in 0..<element { | |
| node = node!.next | |
| } | |
| return node | |
| } | |
| public func removeAll() { | |
| head = nil | |
| tail = nil | |
| } | |
| public func remove(at index: Int) -> Element? { | |
| //TODO: Remove prevNode and nextNode | |
| var node = head | |
| var prevNode = node | |
| var nextNode = node | |
| var element: Element? | |
| for i in 0...index { | |
| if i == index { | |
| // Element to remove is head. | |
| if index == 0 { | |
| head = head!.next | |
| } | |
| // Element to remove is tail. | |
| else if node!.next == nil { | |
| tail = prevNode | |
| tail!.next = nil | |
| } | |
| // Element to remove is in between head and tail. | |
| else if let next = node!.next { | |
| nextNode = next | |
| prevNode!.next = nextNode | |
| } | |
| element = node!.element | |
| } else { | |
| prevNode = node | |
| } | |
| node = node!.next | |
| } | |
| return element | |
| } | |
| public func remove(node: SinglyLinkedListNode<Element>) -> SinglyLinkedListNode<Element>? { | |
| // Find previous node | |
| var prev = head | |
| while prev! != node { | |
| prev = prev!.next | |
| } | |
| let next = node.next | |
| // Removing element inbetween head and tail | |
| if let prev = prev { | |
| prev.next = next | |
| } else { | |
| // Removing head | |
| head = next | |
| } | |
| // Removing tail | |
| if next == nil { | |
| tail = prev | |
| } | |
| node.next = nil | |
| return node | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class SinglyLinkedListNode<Element> { | |
| public var element: Element | |
| public var next: SinglyLinkedListNode<Element>? | |
| init(_ element: Element) { | |
| self.element = element | |
| } | |
| } | |
| extension SinglyLinkedListNode: Equatable { | |
| public static func == (lhs: SinglyLinkedListNode, rhs: SinglyLinkedListNode) -> Bool { | |
| return | |
| lhs.next == rhs.next | |
| } | |
| } |
Doubly Linked List
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class DoublyLinkedList<Element> { | |
| private var head: DoublyLinkedListNode<Element>? | |
| private var tail: DoublyLinkedListNode<Element>? | |
| public var first: DoublyLinkedListNode<Element>? { | |
| return head | |
| } | |
| public var last: DoublyLinkedListNode<Element>? { | |
| return tail | |
| } | |
| public var isEmpty: Bool { | |
| return head == nil | |
| } | |
| public var count: Int { | |
| var node = head | |
| var count = 0 | |
| while node != nil { | |
| count += 1 | |
| node = node!.next | |
| } | |
| return count | |
| } | |
| public func append(_ element: Element) { | |
| let node = DoublyLinkedListNode(element) | |
| if isEmpty { | |
| head = node | |
| } else { | |
| node.prev = tail | |
| tail!.next = node | |
| } | |
| tail = node | |
| } | |
| public func index(of element: Int) -> DoublyLinkedListNode<Element>? { | |
| if element < 0, head == nil { | |
| return nil | |
| } | |
| var node = head | |
| for _ in 0..<element { | |
| node = node!.next | |
| } | |
| return node | |
| } | |
| public func removeAll() { | |
| head = nil | |
| tail = nil | |
| } | |
| public func remove(at index: Int) -> DoublyLinkedListNode<Element>? { | |
| var node = head | |
| for i in 0...index { | |
| if i == index { | |
| if index == 0 { | |
| head = node!.next | |
| head!.prev = nil | |
| } | |
| else if node!.next == nil { | |
| tail = node!.prev | |
| tail!.next = nil | |
| } | |
| else { | |
| node!.prev!.next = node!.next | |
| node!.next!.prev = node!.prev | |
| } | |
| } | |
| node = node!.next | |
| } | |
| return node | |
| } | |
| public func remove(node: DoublyLinkedListNode<Element>) -> DoublyLinkedListNode<Element>? { | |
| let prev = node.prev | |
| let next = node.next | |
| // Removing element inbetween head and tail | |
| if let prev = prev { | |
| prev.next = next | |
| } else { | |
| // Removing head | |
| head = next | |
| } | |
| next?.prev = prev | |
| // Removing tail | |
| if next == nil { | |
| tail = prev | |
| } | |
| node.prev = nil | |
| node.next = nil | |
| return node | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class DoublyLinkedListNode<Element> { | |
| public var prev: DoublyLinkedListNode<Element>? | |
| public var next: DoublyLinkedListNode<Element>? | |
| public var element: Element | |
| init(_ element: Element) { | |
| self.element = element | |
| } | |
| } |
AWESOME POST……………………….