loading...

Linked list implementation in Swift

momin96 profile image Nasir Ahmed Momin ・4 min read

Linked list according to Wikipedia:
It's a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes that together represent a sequence.

Types of a linked list.

  1. Singly.
  2. Doubly.
  3. Circular.
  4. And many more.

Operations that we are going to perform.

  1. Add a node from left/right.
  2. Remove Node from left/right.
  3. Size of the list.
  4. Search data in the list.

Here we 'll see only a Singly list.
Alt Text

Let's define the structure for List

struct Node<T> {
   var data: T?
   var next: Node<T>?

   init(_ data: T) {
       self.data = data
   }
}

As soon as to define this structure, you 'll hit with compilation error.
Alt Text

Due to the nature of struct this issue obvious, as the compiler must know the size of struct in compile time. In this case, struct refers to itself which means there no definite size.
To resolve it, just change from struct (value type) to class (reference type).

class Node<T>{

Here we are using a generic type called <T> so that we can hold any type of data in the list.

Define an enum as direction for node manipulation.

enum ListDirection {
    case left
    case right
}

Define a structure for SinglyLinkedList & functions to implement as shown below.

struct SinglyLinkedList {

    // If nil, then there is NO node in list sequence.
    var firstNode: Node<T>?

    // Adds data/Item by creating node from specified direction.
    mutating func add(anItem item: T, from d: ListDirection) { }

    // Remove item from from specified direction.
    mutating func remove(from d: ListDirection) -> Node<T>? { }

    // fetch number of nodes available in linked list
    func getListSize() -> Int? { }

    // Search for item/data existance in list, returns true or false
    func search(anItem item: T?) -> Bool { }

    // Displays content of list
    func showListContent() { }
}

Let's start the implementation of those function, the explanation will be available inline.

add(anItem:from:) function

// Adds data/Item by creating node from a specified direction.
mutating func add(anItem item: T, from d: ListDirection) {

    // Create node by supplied data, to be added in list
    let newNode = Node<T>(item)

    // Validation check for node list does NOT exist, if true then, make new node as firstNode
    if firstNode == nil {
        self.firstNode = newNode
    }
    else {

        // Obtain firstNode reference.
        var tempNode = self.firstNode

        if d == .left { // Validation check for data insertion from Left side.
            // Make tempNode as next sequence for newly created node.
            newNode.next = tempNode

            // Make newNode as first node, so that new data empbed on left side.
            self.firstNode = newNode

        }
        else if d == .right { // Validation check for data insertion from Right side.

            // Note that the first node is never manipulated in this clause.
            // Traverse till it reaches nil
            while tempNode?.next != nil {
                tempNode = tempNode?.next
            }

            // Then insert new node from right side.
            tempNode?.next = newNode
        }
    }
}

Now create an instance of a singly linked list & start adding items in it.

var ll = SinglyLinkedList<Int>()
ll.add(anItem: 10, from: .left)
ll.add(anItem: 20, from: .right)
ll.add(anItem: 30, from: .left)
ll.add(anItem: 40, from: .left)
ll.add(anItem: 50, from: .right)
ll.add(anItem: 60, from: .right)

Once we added items there is no way we can see it in action, for that we required a showListContent() function. Below is the implementation of it.

// Displays content of list
func showListContent() {

    // Visible string to display sequence of data in list
    var visibleNodeSequence: String = ""

    var tempNode = self.firstNode

    // Travese till reaches end of list
    while tempNode != nil {

        if let str = tempNode?.data {
            visibleNodeSequence.append(contentsOf: String(describing:str))
            visibleNodeSequence.append(contentsOf:  tempNode?.next != nil ? " -> " : "")
        }

        // Incrementing by pointing to next node
        tempNode = tempNode?.next
    }

    print(visibleNodeSequence)
}

// Display content of list
ll.showListContent()

On console, you can see output like this.
Alt Text

remove(from:) -> Node<T>? function

// Remove item from from specified direction.
mutating func remove(from d: ListDirection) -> Node<T>? {

    var nodeToBeRemoved: Node<T>?

    // return nil, incase of NO sequence exist
    if self.firstNode == nil {
        return nil
    }

    var nextNode = self.firstNode

    if d == .left {
        // Makes sure firstNode's next node becomes firstNode. so that firstNode from left side can be removed.
        self.firstNode = nextNode?.next
        nodeToBeRemoved = nextNode
    }
    else if d == .right {
        // Maintains a previous node, so that connection for node to be removed is deleted.
        var prevnode: Node<T>? = self.firstNode

        // Traverse till it reaches nil node
        while nextNode?.next != nil {
            // Both points to same node, then next node is incremented to point to next of next
            prevnode = nextNode
            nextNode = nextNode?.next
        }

        // Connection deleting for node to be removed
        prevnode?.next = nil
        nodeToBeRemoved = nextNode
    }

    return nodeToBeRemoved
}

getListSize()->Int? function

// fetch number of nodes available in linked list
func getListSize() -> Int? {

    // Validation check for first node is nil.
    guard firstNode != nil else { return nil }

    var tempNode = firstNode

    // Maintian a counter to loop
    var noOfNodes = 0

    // Traverse till it reaches nil node
    while tempNode != nil {
        // If not nil then increment counter
        noOfNodes += 1
        // Increment node by pointing to next node
        tempNode = tempNode?.next
    }

    return noOfNodes
}

// Get size of linked list
ll.getListSize()

search(anItem:) -> Bool function

// Search for item/data existance in list, returns true or false
func search(anItem item: T?) -> Bool {

    guard firstNode != nil else { return false }

    var tempNode = self.firstNode

    while tempNode != nil {

        if tempNode?.data == item {
            // Once item exist return true.
            return true
        }

        // Increment node by pointing to next node
        tempNode = tempNode?.next
    }

    return false
}

// Searches item 40 in list
ll.search(anItem: 40)

Discussion

pic
Editor guide