how to create linked list in swift

Linked List in Swift

(Last Updated On: September 25, 2021)

A linked list is a collection of values arranged in a linear unidirectional sequence. Linked List in Swift can be implemented using the code shared in this blog post.

In this blog post, I am sharing the code that I wrote for creating a linked list. This is not a detailed blog post about what linked list, but just a reference code to create a linked list.

import Foundation

//MARK: Creating a Node

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

extension Node : CustomStringConvertible {
    public var description : String {
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) --> " + String(describing: next) + " "
    }
}

//MARK: Creating a Linked List

public struct LinkedList<Value> {
    
    public var head : Node<Value>?
    public var tail : Node<Value>?
    
    public init() { }
    
    //MARK: Insert
    ///head-end insertion
    
    /*
     In swift, structs are immutable objects. by using mutating keyword in below function, the function will return a new struct in place. The mutating keyword lets the caller know that this method is going to make the value change.
     */
    
    public mutating func push(_ value : Value) {
        head = Node(value: value, next: head)
        if tail == nil {
            tail = head
        }
    }
    
    ///tail-end insertion
    
    public mutating func append(_ value : Value) {
        
        guard !isEmpty else {
            push(value)
            return
        }
        
        tail!.next = Node(value: value, next: nil)
        tail = tail!.next
    }
    
    ///insert-after
    
    public mutating func insert(value : Value, after node: Node<Value>) {
       
        guard tail !== head else {
            self.append(value)
            return
        }
        
        node.next = Node(value: value, next: node.next)
        
        
    }
    
    //MARK: Delete
    ///delete first
    @discardableResult
    public mutating func pop() -> Value? {
        defer {
            head = head?.next
            if isEmpty {
                tail = nil
            }
        }
        return head?.value
    }
    
    /// delete last
    
    @discardableResult
    public mutating func removeLast() -> Value? {
        // check if list is not empty.
        guard let head = head else {
            return nil
        }
        // if list contains only one element
        guard head.next != nil else {
            return pop()
        }
        var prev = head
        var current = head
        
        while let next = current.next {
            prev = current
            current = next
        }
        prev.next = nil
        tail = prev
        return current.value
        
    }
    
    ///delete at index
    
    public mutating func remove(after node : Node<Value>) -> Value? {
        // check if head next is tale
        defer {
            if node.next === tail {
                tail = node
            }
            node.next = node.next?.next
        }
        return node.next?.value
    }
    
    /// get node at index
    public func node(at index : Int) -> Node<Value>? {
        var currentNode = head
        var currentIndex = 0
        
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode!.next
            currentIndex = currentIndex + 1
        }
        
        return currentNode
    }

}

extension LinkedList : CustomStringConvertible {
    public var description: String {
        guard let head = head else {
            return "Empty Linked List"
        }
        return String(describing: head)
    }
}

extension LinkedList : Collection {
  
    public var isEmpty : Bool {
        return head == nil
    }
    
    //MARK: Comparable
    public struct Index : Comparable {
   
        
        public var node : Node<Value>?
        
        static public func ==(lhs: Index , rhs: Index) -> Bool {
            switch (lhs.node,rhs.node) {
            case let (left? , right?):
                return left.next === right.next
            case (nil,nil):
                return true
            default:
                return false
            }
        }
        
        static public func <(lhs: Index , rhs: Index) -> Bool {
            guard lhs != rhs else {
                return false
            }
            let nodes = sequence(first: lhs.node) { $0?.next }
            return nodes.contains { $0 === rhs.node }
        }
        
    }
    
    //MARK: Collection and Sequence Protocol
    
    public func index(after i: Index) -> Index {
        return Index(node: i.node?.next)
    }
    
    public subscript(position: Index) -> Value {
        return position.node!.value
    }
    
    
    public var startIndex: Index {
        return Index(node: head)
    }
    
    public var endIndex: Index {
        return Index(node: tail)
    }
}

1 Comment

Leave a Comment