✍️ 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
You must be logged in to post a comment.