Linked list implementation in Swift
Tags: swift, linkedlist, datastructure
Published: 2020-01-19 05:01:46

**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](https://thepracticaldev.s3.amazonaws.com/i/6y4dwqe14o4pi62bywnu.png)


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](https://thepracticaldev.s3.amazonaws.com/i/bus5p9bar0s3xvqzn0xl.png)

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](https://thepracticaldev.s3.amazonaws.com/i/7m4c384gugl2zxhuwrid.png)

  
`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)