Linked List in Swift

by

A Linked List is a linear data structure where we can store data sequentially. Elements of a Linked List called nodes, are linked using pointers. Here is a visual representation of the linked list with three elements:

Each node contains two main components: the data and a reference (or pointer) to the next node in the sequence.

Types of Linked Lists:

  • Singly Linked List: Each node contains a reference to the next node. The above example is a Singly Linked List.
  • Doubly Linked List: Each node contains two references, one to the next node and one to the previous node.
  • Circular Linked List: The last node points back to the first node, forming a circle. A circular linked list can be doubly too.

Components of a Linked List

Node

A node is an individual part of a linked list that contains data and a reference to the next node. We can implement Node using class or structure. Here is an implementation of a Node in Swift using Class:

class Node<T> {
    var value: T
    var next: Node?
    
    init(value: T) {
        self.value = value
        self.next = nil
    }
}

Linked List

The linked list itself maintains a reference to the first node (head). If we maintain a reference to the last node (tail), append operations will be easier. Here is the LinkedList Class implementation in Swift: 

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
}

We have created Node and LinkedList, to make it useful, we have to implement various methods like append, remove, etc. Let’s try to add the append method first:

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?

    // Append a value at the end
    func append(_ value: T) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
}

Now if we initialize LinkedList, we will able to append value to it. Here is the full program so far:

class Node<T> {
    var value: T
    var next: Node?
    
    init(value: T) {
        self.value = value
        self.next = nil
    }
}

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?

    // Append a value at the end
    func append(_ value: T) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
}


// Usage
var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)

We can add a method to print all elements from LinkedList like this:

// Print all values in the list
    func printList() {
        var current = head
        while let node = current {
            print(node.value)
            current = node.next
        }
    }

After adding this method to the LinkedList class, we can call this method. It will print all items from our list. So that, we can verify our LinkedList Class working as expected: 

list.printList()

Standard operations of a LinkedList:

Standard operations of LinkedList are:

  • Append elements
  • Remove elements
  • Checking is empty
  • Traverse elements
  • Search
  • Sort etc.

Here is an example of LinkedList with some essential methods:

class Node<T> {
    var value: T
    var next: Node?

    init(value: T) {
        self.value = value
        self.next = nil
    }
}

class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?

    // Check if the list is empty
    var isEmpty: Bool {
        return head == nil
    }

    // Get the first node
    var first: Node<T>? {
        return head
    }

    // Get the last node
    var last: Node<T>? {
        return tail
    }

    // Append a value at the end
    func append(_ value: T) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }

    // Remove the first node
    func removeFirst() -> T? {
        let firstValue = head?.value
        head = head?.next
        if head == nil {
            tail = nil
        }
        return firstValue
    }

    // Remove all nodes
    func removeAll() {
        head = nil
        tail = nil
    }

    // Print all values in the list
    func printList() {
        var current = head
        while let node = current {
            print(node.value)
            current = node.next
        }
    }
}

// Usage
let list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)

list.printList() // Output: 1 2 3

list.removeFirst()
list.printList() // Output: 2 3

list.removeAll()
list.printList() // Output: (nothing, as the list is now empty)

Pros and Cons of LinkedList

Advantages of Linked Lists

  1. Dynamic Size: The size of a linked list can grow or shrink dynamically.
  2. Efficient Insertions/Deletions: Adding or removing elements is efficient, especially at the beginning or end of the list.

Disadvantages of Linked Lists

  1. Memory Overhead: Each node requires additional memory for storing the reference to the next node.
  2. Sequential Access: Linked lists do not allow random access to elements. To access an element, you have to traverse the list from the beginning.

Applications of Linked Lists

  • Implementation of Stacks and Queues: Linked lists are often used to implement other abstract data types such as stacks and queues.
  • Graph Adjacency List: In graph representations, linked lists can be used to store adjacency lists.
  • Dynamic Memory Allocation: Linked lists can be used to manage free memory in dynamic memory allocation schemes.

Leave a Reply