Swift, Data Structure – Linked List

✍️ Note

Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts

What is Linked List

It is a list data structure where each element in the list holds some information and points to where the next element lies.

Linked List vs Arrays

Linked List

List sizes are unlimited, you don’t need to know up front how many elements will be added to the linked list, the size of the linked list can grow dynamically

Inserting a new element in a linked list is a very easy operation, the logical next pointers have to be reassigned but not much else needs to be done

Similarly deleting an element in a list is very easy and efficient

Random access to an element at a specific index in the linked list is not possible. The entire list up-to that element has to be traversed

Each element requires additional space to store a pointer to the next element

Cannot take advantage of spatial locality (for caching) when accessing the elements

Each element can live pretty much anywhere in memory and be pointed to

Arrays

Arrays have to be declared upfront with the number of elements it will hold, the size of array cannot be increased dynamically <- In Swift, You can increase size, You can read details at Apple Document – Growing the Size of an Array

Arrays are located in contiguous memory locations, in order to insert an element, the elements to it’s right have to move over to make room for it. It is a more heavyweight operation.

Array elements have to be moved in the case of deletion as well

Arrays provide very quick lookup for elements at specific indices, since they are in contiguous memory locations, we know exactly where in memory the element is

No extra space is required other than for the actual elements which make up the array

As elements are in contiguous memory locations access to arrays takes significant advantage of spatial locality in caches

This can be a significant performance improvement

Use Linked Lists when

You have a large number of insert or delete operations to perform

You have no idea how large your list might be

Use Array when

Read operations need to be extremely fast and you have relatively few updates to the array

You require random access to array elements

Source: https://www.udemy.com/course/from-0-to-1-data-structures/learn/lecture/8504232#content

Last element points to nil

First element is head

class Node {
    let value: Int
    var next: Node?
    init(value: Int, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

let head = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
let fourth = Node(value: 4)

//Make linked list
head.next = second
second.next = third
third.next = fourth
fourth.next = nil

var start: Node? = head

while start != nil {
    print("\(start!.value)")
    var next = start?.next
    start = next
}

//Prints
1
2
3
4

Exercise 1. Get Length of a linked list

func length(of linkedList: Node?) -> Int {
    var length = 0
    var head = linkedList
    while head != nil {
        length += 1
        head = head?.next
    }
    return length
}

length(of: head)

Exercise 2. Get the N-th element in a Linked List

func element(of linkedList: Node?, at index: Int) -> Node? {
    if index < 0 {
        return nil
    }
    var length = 0
    var head = linkedList
    while head != nil {
        if index == length {
            return head
        }
        length += 1
        head = head?.next
    }
    return nil
}

// 1 -> 2 -> 3 -> 4, Index 3 is 4
element(of: head, at: 3)?.value //Prints 4, It's correct

Exercise 3. Append an element to the end of a linked list

There is 2 case you need to handle

head is null -> create a head node
there is a linked list, create a new node and append it as a last node. Don’t forget to handle last node’s next is nil

var head: Node? = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
let fourth = Node(value: 4)

//Make linked list
head?.next = second
second.next = third
third.next = fourth
fourth.next = nil

func print(linkedList: Node?) {
    var head = linkedList
    while head != nil {
        print("\(head!.value)")
        head = head?.next
    }
}

//To handle if linkedList is nil, and You don't want to return anything then use inout parameter.
func append(data: Int, at linkedList: inout Node?) {
    if linkedList == nil {
        linkedList = Node(value: data)
        return
    }
    var head = linkedList
    var lastItem: Node?
    while linkedList?.next != nil {
        linkedList = linkedList?.next
    }
    lastItem = linkedList
    lastItem?.next = Node(value: data)
    //Important, Reset head node
    linkedList = head
}

var emptyHead: Node?
//Case 1. Empty Head
append(data: 4, at: &emptyHead)
print(emptyHead?.value)

//Case 2. 1 -> 2 -> 3 -> 4, append 5
append(data: 5, at: &head)
print(linkedList: head)

Exercise 4. Remove the first element

func removeFirst(linkedList: inout Node?) {
    guard linkedList != nil else {
        return
    }
    var head: Node? = linkedList
    head = head?.next
    linkedList = head
}
print("LinkedList")
print(linkedList: head)

removeFirst(linkedList: &head)
print("Removed:")
print(linkedList: head)

//Prints
LinkedList
1
2
3
4
Removed:
2
3
4

Exercise 5. Delete all the elements (All nodes should be removed from Memory)

class Node {
    let value: Int
    var next: Node?
    init(value: Int, next: Node? = nil) {
        self.value = value
        self.next = next
    }
    
    deinit {
        print("Node \(value) is deinit")
    }
}

func removeAll(linkedList: inout Node?) {
    guard linkedList != nil else {
        return
    }
    while linkedList != nil {
        print("Remove : \(linkedList!.value) Refcount: \(CFGetRetainCount(linkedList))")
        var next = linkedList?.next
        linkedList?.next = nil
        linkedList = next
    }
}

//Prints
Remove : 1 Refcount: 2
Node 1 is deinit
Remove : 2 Refcount: 3
Remove : 3 Refcount: 3
Remove : 4 Refcount: 3

What’s wrong? Only Node 1 deinit. The rest of nodes are still remaining in Memory.

To remove all nodes from Memory, We need to fix previous example of linked list.

Let’s make a linkedList function.

func linkedList(_ input: [Int]) -> Node? {
    guard input.count > 0 else {
        return nil
    }
    var head: Node? = Node(value: input.first!)
    var linkedList = head
    for i in 1..<input.count {
        let value = input[i]
        linkedList?.next = Node(value: value)
        linkedList = linkedList?.next
    }
    return head
}

var newList = linkedList([1, 2, 3, 4])
removeAll(linkedList: &newList)

//Prints
Remove : 1 Refcount: 2
Node 1 is deinit
Remove : 2 Refcount: 2
Node 2 is deinit
Remove : 3 Refcount: 2
Node 3 is deinit
Remove : 4 Refcount: 2
Node 4 is deinit

I used a same removeAll function. I only change the linkedList by using linkedList function. This function returns linkedList and all nodes has a same reference counts.

Now You can see all nodes are completely removed from Memory.

Next example, I’ll continue use linkedList function for creating a linked list.

Exercise 6. Insert an elements at index

func print(linkedList: Node?) {
    var head = linkedList
    while head != nil {
        print("\(head!.value)", terminator: head?.next == nil ? "" : " -> ")
        head = head?.next
    }
}

func insert(value: Int, at index: Int, in linkedList: inout Node?) {
    guard linkedList != nil else {
        return
    }
    var head = linkedList
    //Edge case
    if index == 0 {
        var newHead = Node(value: value, next: linkedList)
        linkedList = newHead
        return
    }
    for i in 0..<index - 1 {
        var next = linkedList?.next
        linkedList = next
    }
    var prevItem = linkedList
    var prevNextItem = prevItem?.next
    prevItem?.next = Node(value: value)
    prevItem?.next?.next = prevNextItem
    
    //Pointing to head node
    linkedList = head
}
var newList = linkedList([1, 2, 3, 4])

//MARK: Print All nodes
print("Current List")
print(linkedList: newList)
print("\n")

insert(value: 9, at: 2, in: &newList)
print("After insert 9 at index 2")
print(linkedList: newList)


print("\n")
insert(value: 10, at: 0, in: &newList)
print("After insert 10 at index 0")
print(linkedList: newList)

//Prints
Current List
1 -> 2 -> 3 -> 4

After insert 9 at index 2
1 -> 2 -> 9 -> 3 -> 4

After insert 10 at index 0
10 -> 1 -> 2 -> 9 -> 3 -> 4

Example 7. Insert an element at the right position in Sorted Linked List

func insert(value: Int, in sortedLinkedList: inout Node?) {
    guard sortedLinkedList != nil else {
        return
    }
    var head = sortedLinkedList
    while sortedLinkedList != nil, sortedLinkedList!.value < value  {
        var next = sortedLinkedList?.next
        if let nextValue = next?.value, nextValue > value {
            break
        }
        else {
            sortedLinkedList = sortedLinkedList?.next
        }
    }
    var prevItem = sortedLinkedList
    var prevNextItem = prevItem?.next
    prevItem?.next = Node(value: value)
    prevItem?.next?.next = prevNextItem
    
    //Pointing to head node
    sortedLinkedList = head
}

var newList = linkedList([1, 2, 3, 5])

//MARK: Print All nodes
print("Current List")
print(linkedList: newList)
print("\n")

insert(value: 4, in: &newList)
print("After insert 4 in sorted LinkedList")
print(linkedList: newList)

//Prints
Current List
1 -> 2 -> 3 -> 5

After insert 4 in sorted LinkedList
1 -> 2 -> 3 -> 4 -> 5

Example 8. Append one linked list to the end of another

func append(a: inout Node?, b: inout Node?) {
    var mergedLinkedListHeader = a
    
    while a?.next != nil {
        a = a?.next
    }
    a?.next = b
    a = mergedLinkedListHeader
    b = mergedLinkedListHeader
}

var a = linkedList([1, 2, 3, 4])
var b = linkedList([5, 6, 7, 8])

//MARK: Print All nodes
print("A: Linked List")
print(linkedList: a)
print("\n")

print("B: Linked List")
print(linkedList: b)
print("\n")

print("A+B")
append(a: &a, b: &b)
print(linkedList: a)
print("\n")

//Prints
A: Linked List
1 -> 2 -> 3 -> 4

B: Linked List
5 -> 6 -> 7 -> 8

A+B
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Example 9. Split one Linked List to two Linked List, find a mid point and split it!

🤔 Wait, why use 2 pointer?

Without 2 pointer, You need to get a length of linkedList first and then iterate linkedList again to split it.

func split(list: inout Node?) -> (first: Node?, seconds: Node?) {
    var firstNode: Node? = list
    var secondsNode: Node?
    
    //for 1 step
    var slowPointer = list
    //for 2 steps
    var fastPointer = list?.next
    
    while fastPointer?.next != nil {
        slowPointer = slowPointer?.next
        fastPointer = fastPointer?.next?.next
    }
    //Split first list
    secondsNode = slowPointer?.next
    slowPointer?.next = nil
    return (firstNode, secondsNode)
}

Test case 1. Input = [1, 2, 3, 4, 5, 6, 7, 8]

var list = linkedList([1, 2, 3, 4, 5, 6, 7, 8])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")

var (firstSubList, secondsSublist) = split(list: &list)

print("First Sub Linked List")
print(linkedList: firstSubList)
print("\n")

print("Seconds Sub Linked List")
print(linkedList: secondsSublist)
print("\n")

/Prints
Linked List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

First Sub Linked List
1 -> 2 -> 3 -> 4

Seconds Sub Linked List
5 -> 6 -> 7 -> 8

Test case 2. Input = [1, 2, 3, 4, 5, 6, 7]

var list = linkedList([1, 2, 3, 4, 5, 6, 7])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")

var (firstSubList, secondsSublist) = split(list: &list)

print("First Sub Linked List")
print(linkedList: firstSubList)
print("\n")

print("Seconds Sub Linked List")
print(linkedList: secondsSublist)
print("\n")

//Prints
Linked List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

First Sub Linked List
1 -> 2 -> 3 -> 4

Seconds Sub Linked List
5 -> 6 -> 7

Example 10. Remove duplicate nodes in a sorted linked list

func removeDuplicates(linkedList: inout Node?) {
    var head: Node? = linkedList
    while linkedList?.next != nil {
        var nextNode = linkedList?.next
        //Check duplicates
        if linkedList?.value == nextNode?.value {
            while nextNode?.value == nextNode?.next?.value {
                var tempNext = nextNode?.next
                nextNode = tempNext
            }
            linkedList?.next = nextNode?.next
        }
        linkedList = linkedList?.next
    }
    linkedList = head
}

var list = linkedList([1, 2, 3, 3, 3, 4, 4, 5])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")


removeDuplicates(linkedList: &list)
print("Removed duplicates in Linked List")
print(linkedList: list)
print("\n")

Example 11. Move node from the head of one list and add to the front of another

func moveHeadToAnother(source: inout Node?, dest: inout Node?) {
    var sourceHead = source
    source = source?.next
    
    var destHead = dest
    sourceHead?.next = destHead
    dest = sourceHead
}

var source = linkedList([1, 2, 3])
var dest = linkedList([7, 8, 9])
//MARK: Print All nodes
print("Source Linked List")
print(linkedList: source)
print("\n")

print("Destination Linked List")
print(linkedList: dest)
print("\n")

moveHeadToAnother(source: &source, dest: &dest)
print("Result: Source Linked List")
print(linkedList: source)
print("\n")

print("Result: Destination Linked List")
print(linkedList: dest)
print("\n")

//Prints
Source Linked List
1 -> 2 -> 3

Destination Linked List
7 -> 8 -> 9

Result: Source Linked List
2 -> 3

Result: Destination Linked List
1 -> 7 -> 8 -> 9

🤯 Example 12. Merge two sorted linked list and then return a new sorted linked list

func merge(a: Node?, b: Node?) -> Node? {
    //Edge cases
    if a == nil, b == nil {
        return nil
    }
    if a == nil, b != nil {
        return b
    }
    if a != nil, b == nil {
        return a
    }
    
    var result: Node?
    var resultHead: Node?
    var headA = a
    var headB = b
    
    if headA!.value < headB!.value {
        resultHead = headA
        headA = headA?.next
    }
    else {
        resultHead = headB
        headB = headB?.next
    }
    resultHead?.next = nil
    result = resultHead
    
    while headA != nil && headB != nil {
        if headA!.value < headB!.value {
            result?.next = headA
            headA = headA?.next
        }
        else {
            result?.next = headB
            headB = headB?.next
        }
        result = result?.next
    }
    //Add rest of nodes
    var restNodes = headA ?? headB
    //When one list runs out make sure the remaining elements of the other are appended to the end of the result
    result?.next = restNodes
    //Pointing to head
    result = resultHead
    return result
}

var listA = linkedList([1, 2, 5])
var listB = linkedList([1, 4, 6])
//MARK: Print All nodes
print("listA Linked List")
print(linkedList: listA)
print("\n")

print("listB Linked List")
print(linkedList: listB)
print("\n")

let mergedList = merge(a: listA, b: listB)
print("Merged Linked List")
print(linkedList: mergedList)
print("\n")

//Prints
listA Linked List
1 -> 2 -> 5

listB Linked List
1 -> 4 -> 6

Merged Linked List
1 -> 1 -> 2 -> 4 -> 5 -> 6

Example 13. Reverse a Linked List

Code

func reverseLinkedList(input: Node?) -> Node? {
    //Prev will become a head of reversed linked list
    var prev = input
    var current = input?.next
    
    //At this time, prev is tail node, but after while loop, It become a head node
    prev?.next = nil
    while current != nil {
        //next node is input's next step
        var next = current?.next
        //It makes reversed direction
        current?.next = prev
        
        //next step for reversed linkedList
        prev = current
        current = next
    }
    return prev
}

var input = linkedList([1, 2, 5])
//MARK: Print All nodes
print("Input Linked List")
print(linkedList: input)
print("\n")

var reversedLinkedList = reverseLinkedList(input: input)

print("Reversed Linked List")
print(linkedList: reversedLinkedList)
print("\n")

//Prints
Input Linked List
1 -> 2 -> 5

Reversed Linked List
5 -> 2 -> 1

Doubly Linked List

A doubly linked list has pointers to the next element as well as pointers to the previous element.

This requires additional memory in every node to store the previous pointer.
https://www.udemy.com/course/break-away-coding-interviews-1/learn/lecture/8462452#content

class Node {
    let value: Int
    var prev: Node?
    var next: Node?
    
    init(value: Int, prev: Node? = nil, next: Node? = nil) {
        self.value = value
        self.prev = prev
        self.next = next
    }
}

func createDoublyLinkedList(input: [Int]) -> Node? {
    guard !input.isEmpty else {
        return nil
    }
    var queue = input
    var head: Node? = Node(value: queue.removeFirst())
    var temp = head
    
    while !queue.isEmpty {
        var currentNode = Node(value: queue.removeFirst())
        temp?.next = currentNode
        currentNode.prev = temp
        //Pointing to the next
        temp = currentNode
    }
    return head
}

func printAll(head: Node?) {
    guard let head else {
        return
    }
    var node: Node? = head
    while node != nil {
        
        print("Node: \(node!.value), prev: \(node?.prev?.value) next: \(node?.next?.value)", terminator: node?.next == nil ? "" : " <-> ")
        node = node?.next
    }
}


var head = createDoublyLinkedList(input: [1, 2, 3])
printAll(head: head)

//Prints
current: 1, prev: nil next: Optional(2) <-> current: 2, prev: Optional(1) next: Optional(3) <-> current: 3, prev: Optional(2) next: nil

Deleting a node in a doubly linked list

Notes. Consider edge cases

Delete head
Delete tail
Delete node

class Node {
    let value: Int
    var prev: Node?
    var next: Node?
    
    init(value: Int, prev: Node? = nil, next: Node? = nil) {
        self.value = value
        self.prev = prev
        self.next = next
    }
    
    deinit {
        print("🔥 deinit: \(value)")
    }
}

func createDoublyLinkedList(input: [Int]) -> Node? {
    guard !input.isEmpty else {
        return nil
    }
    var queue = input
    var head: Node? = Node(value: queue.removeFirst())
    var temp = head
    
    while !queue.isEmpty {
        var currentNode = Node(value: queue.removeFirst())
        temp?.next = currentNode
        currentNode.prev = temp
        //Pointing to the next
        temp = currentNode
    }
    return head
}

func printAll(head: Node?) {
    guard let head else {
        return
    }
    var node: Node? = head
    while node != nil {
        print("Node: \(node!.value), prev: \(node?.prev?.value) next: \(node?.next?.value)", terminator: node?.next == nil ? "" : " <-> ")
        node = node?.next
    }
    print("\n")
}

func delete(value: Int, in linkedList: inout Node?) {
    guard linkedList != nil else {
        return
    }
    print("Delete : \(value)")
    var head: Node? = linkedList
    var temp: Node? = head
    
    //Step find node to be deleted
    while temp != nil && temp?.value != value {
        temp = temp?.next
    }

    //Edge case, Not found value
    if temp == nil {
        return
    }
    
    //Unlink
    if temp?.prev != nil {
        temp?.prev?.next = temp?.next
    }
    else {
        //Edge case, It deleting node is head, set new head
        linkedList = temp?.next
        //Note, after removed the node, new head's prev became nil because It removed from memory
    }
    
    if temp?.next != nil {
        temp?.next?.prev = temp?.prev
    }
}

var head = createDoublyLinkedList(input: [1, 2, 3])
printAll(head: head)
delete(value: 1, in: &head)

print("\nAfter delete\n")
printAll(head: head)

//Prints
Node: 1, prev: nil next: Optional(2) <-> Node: 2, prev: Optional(1) next: Optional(3) <-> Node: 3, prev: Optional(2) next: nil

Delete : 1
🔥 deinit: 1

After delete

Node: 2, prev: nil next: Optional(3) <-> Node: 3, prev: Optional(2) next: nil

Shawn