Swift Linked List With Examples [Latest]

What is LinkedList?

LinkedList is a type of Data structure that holds the data linearly/sequentially.

Typically, we call every element of a LinkedList as a Node.

So every Node consists of the value and a reference to the next element.

Following diagram illustrates a Node.

A LinkedList is simply a list of nodes where every node stores a reference for it’s next node.

The first Node is typically referred to as the HEAD. The LinkedList finishes when the NEXT of the last node is a Nil.

A Doubly LinkedList stores the reference for it’s previous and next nodes both.

In the following section, we’ll create Node structure and do various operations on LinkedList such as:

• appending new element
• Size of the LinkedList
• inserting an element at a position
• deleting element
• printing the LinkedList forward and backward
• Retrieving the Node from a particular position

Open your Xcode Playground and lets Swift!

Create a Swift LinkedList Node

We can create a Node of Generic type as shown below:

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

SNode represents an instance of Node of the LinkedList.

Let’s create a class SingleLinkedList<T> in which we’ll create and modify our LinkedList

class SingleLinkedList<T> {
    var head: SNode<T>? // head is nil when list is empty
    public var isEmpty: Bool {
        return head == nil
    }
    public var first: SNode<T>? {
        return head
    }

isEmpty is a property that checks if the LinkedList is empty or not. If the head is nil the LinkedList would be empty.

Appending Elements in a Swift LinkedList

Add the following append function in the above class.

public func append(value: T) {
        let newNode = SNode(value: value)
        if var h = head {
            while h.next != nil {
                h = h.next!
            }
            h.next = newNode
        } else {
            head = newNode
        }
    }

The append function adds a new Node to the end of the list. For this, we traverse to the end of the LinkedList using a temporary Node reference of the header named h

When the next reference of h is nil, it means we are at the end of the LinkedList. We set the newNode here by setting the next of the last Node to it.

Inserting an Element at a Position

To insert an element at a position, we need to :
set the previous Node NEXT reference to the new element. Set the NEXT of the new element to the current element present at that point.

Add the following function insert to our above LinkedList class.

func insert(data : T, at position : Int) {
        let newNode = SNode(value: data)
        if (position == 0) {
            newNode.next = head
            head = newNode
        }
        else {
            var previous = head
            var current = head
            for _ in 0..<position {
                previous = current
                current = current?.next
            }
            newNode.next = previous?.next
            previous?.next = newNode
        }
    }

Deleting a Node from the Swift LinkedList

To delete a Node we need to set the reference of the previous Node to the NEXT of the node to be deleted.

Add the following function in the above class.

func deleteNode(at position: Int)
    {
        if head == nil{
        return
        }
        var temp = head
        if (position == 0)
        {
            head = temp?.next;   // Change head
            return
        }
        for _ in 0..<position-1 where temp != nil {
            temp = temp?.next;
        }
        if temp == nil || temp?.next == nil{
           return
        }
        let nextToNextNode = temp?.next?.next
        temp?.next = nextToNextNode
    }

Printing Elements

To print the elements we need to traverse the LinkedList until we reach the last element and print the elements along the way.

To print the elements in reverse order we use recursive functions!

func printList() {
        var current: SNode? = head
        //assign the next instance
        while (current != nil) {
            print("LL item is: (current?.value as? Int ?? 0)")
            current = current?.next
        }
    }
    func printReverseRecursive(node: SNode<T>?) {
    if node == nil{
    return
    }
    printReverseRecursive(node: node?.next)
    print("LL item is: (node?.value as? Int ?? 0)")
    }
    func printReverse() {
        printReverseRecursive(node: first)
    }

Clubbing all the above operations in our class would make our class look like this:

class SingleLinkedList<T> {
    var head: SNode<T>? // head is nil when list is empty
    public var isEmpty: Bool {
        return head == nil
    }
    public var first: SNode<T>? {
        return head
    }
    public func append(value: T) {
        let newNode = SNode(value: value)
        if var h = head {
            while h.next != nil {
                h = h.next!
            }
            h.next = newNode
        } else {
            head = newNode
        }
    }
    func insert(data : T, at position : Int) {
        let newNode = SNode(value: data)
        if (position == 0) {
            newNode.next = head
            head = newNode
        }
        else {
            var previous = head
            var current = head
            for _ in 0..<position {
                previous = current
                current = current?.next
            }
            newNode.next = previous?.next
            previous?.next = newNode
        }
    }
    func deleteNode(at position: Int)
    {
        if head == nil{
        return
        }
        var temp = head
        if (position == 0)
        {
            head = temp?.next
            return
        }
        for _ in 0..<position-1 where temp != nil {
            temp = temp?.next
        }
        if temp == nil || temp?.next == nil{
           return
        }
        let nextToNextNode = temp?.next?.next
        temp?.next = nextToNextNode
    }
    func printList() {
        var current: SNode? = head
        //assign the next instance
        while (current != nil) {
            print("LL item is: (current?.value as? Int ?? 0)")
            current = current?.next
        }
    }
    func printReverseRecursive(node: SNode<T>?) {
    if node == nil{
    return
    }
    printReverseRecursive(node: node?.next)
    print("LL item is: (node?.value as? Int ?? 0)")
    }
    func printReverse() {
        printReverseRecursive(node: first)
    }
}

Let’s add, insert, delete elements from the LinkedList.

let ll = SingleLinkedList<Int>()
ll.append(value: 1)
ll.append(value: 2)
ll.append(value: 4)
ll.insert(data: 5, at: 0)
ll.insert(data: 10, at: 1)
ll.printList()
ll.deleteNode(at: 0)
print("Printing Reverse:")
ll.printReverse()

Following is the output:

Doubly LinkedList

Let’s create a Node for our Doubly LinkedList.

public class DNode<T> {
  var value: T
  var next: DNode<T>?
  weak var previous: DNode<T>?
  init(value: T) {
    self.value = value
  }
}

To prevent memory cycles we’ve set the previous reference as weak.

public class DoublyLinkedList<T> {
  var head: DNode<T>?
  private var tail: DNode<T>?
  public var isEmpty: Bool {
    return head == nil
  }
  //first
  public var first: DNode<T>? {
    return head
  }
  //last
  public var last: DNode<T>? {
    return tail
  }
  //Append node to LinkedList
  public func append(value: T) {
    let newNode = DNode(value: value)
    if let tailNode = tail {
      newNode.previous = tailNode
      tailNode.next = newNode
    } else {
      head = newNode
    }
    tail = newNode
  }
    func insert(node: DNode<T>, at index: Int) {
        if index == 0,
            tail == nil {
            head = node
            tail = node
        } else {
            guard let nodeAtIndex = nodeAt(index: index) else {
                print("Index out of bounds.")
                return
            }
            if nodeAtIndex.previous == nil {
                head = node
            }
            node.previous = nodeAtIndex.previous
            nodeAtIndex.previous?.next = node
            node.next = nodeAtIndex
            nodeAtIndex.previous = node
        }
    }
  //Find Node at Index
  public func nodeAt(index: Int) -> DNode<T>? {
    if index >= 0 {
      var node = head
      var i = index
      while node != nil {
        if i == 0 { return node }
        i -= 1
        node = node!.next
      }
    }
    return nil
  }
  public func removeAll() {
    head = nil
    tail = nil
  }
  //remove Node
  public func remove(node: DNode<T>) -> T {
    let previousNode = node.previous
    let nextNode = node.next
    if let prev = previousNode {
      prev.next = nextNode
    } else {
      head = nextNode
    }
    nextNode?.previous = previousNode
    if nextNode == nil {
      tail = previousNode
    }
    node.previous = nil
    node.next = nil
    return node.value
  }
    var count: Int {
        if (head?.value == nil) {
            return 0
        }
        else {
            var current: DNode? = head
            var x: Int = 1
            //cycle through the list of items
            while ((current?.next) != nil) {
                current = current?.next!
                x = x + 1
            }
            return x
        }
    }
    func printReverse() {
        var current: DNode? = tail;
        //assign the next instance
        while (current != nil) {
            print("DLL item is: (current?.value as? String ?? "NA")")
            current = current?.previous
        }
    }
    func printForward() {
        var current: DNode? = head
        //assign the next instance
        while (current != nil) {
            print("DLL item is: (current?.value as? String ?? "NA")")
            current = current?.next
        }
    }
    //remove from index
    func remove(at index: Int) {
        var toDeleteNode = nodeAt(index: index)
        guard toDeleteNode != nil else {
            print("Index out of bounds.")
            return
        }
        let previousNode = toDeleteNode?.previous
        let nextNode = toDeleteNode?.next
        if previousNode == nil {
            head = nextNode
        }
        if toDeleteNode?.next == nil {
            tail = previousNode
        }
        previousNode?.next = nextNode
        nextNode?.previous = previousNode
        toDeleteNode = nil
    }
}

In the doubly linked list, we take care of both the previous and next references.

let dd = DoublyLinkedList<String>()
dd.append(value: "Harry Potter")
dd.append(value: "Ron")
dd.append(value: "Hermione")
dd.append(value: "Hagrid")
dd.append(value: "Draco")
dd.append(value: "Snape")
//Run the following
print(dd.count)
dd.printReverse()
dd.remove(at: 1)
var dNode = DNode(value: "Harry Potter")
dd.remove(node: dNode)
print(dd.nodeAt(index: 4))
print(dd.nodeAt(index: 10))
dd.insert(node: dNode, at: 4)
dd.printForward()

The output we get from the above operations is:

This brings an end to this tutorial on LinkedList in Swift.