Image for post
Image for post

Data Structures and Algorithms in Swift: Linked List

In part 1 of this series I have talked about Arrays. If you haven’t given it a read, I highly recommend taking a look at it here. In this part of the series I will be writing about another data structure that is very commonly used in problem solving: Linked List.

1. Singly Linked List

2. Doubly Linked List

Let’s talk about Singly Linked List first, from hereon referred to as Linked List. The Node class in a Linked List consists of a data type and a reference to the next Node in the Linked List as shown below:

class Node<T> {  internal var data: T  internal var next: Node<T>?  init(data: T) {    self.data = data    self.next = nil  }
}
Image for post
Image for post
class SinglyLinkedList<T> {  internall var head: Node<T>?  internal var count: Int = 0  public init() {}
init(first: Node<T>) { self.head = first }}
class SinglyLinkedList<T> {  // existing code...  public func isEmpty() -> Bool {
return
count == 0
}
public func size() -> Int {
// return a count of the number of items in the list
return count
}
// adds an element at the beginning of the list
public func add(element: T) {
let node = Node<T>(data: element)
node.next = head
head = node
count += 1
}
// removes and returns an element from the beginning of the list
public func remove() -> T? {
// Check if list is empty
if isEmpty() {
return nil
}
// get the data from the head
let item = self.head?.data
// move the head
self
.head = self.head?.next
// decrease the count
count -= 1
return item
}
}
public func peek() -> T? {  // if list is empty, return nil
if isEmpty() {
return nil
}
// otherwise return the data stored in head
return head?.data
}
// instantiate a singly linked list to store integers
var singlyLinkedList = SinglyLinkedList<Int>()
// add two elements to it
singlyLinkedList.add(element: 2)
singlyLinkedList.add(element: 3)
// print the size and the head element// prints "Size is 2"
print("Size is \(singlyLinkedList.size())")
// prints "Head is 3"
print("Head is \(singlyLinkedList.peek()!)")
// remove the first element
singlyLinkedList.remove()
// peek into the list again// prints "New Head is 2"
print("New Head is \(singlyLinkedList.peek()!)")
class DoublyNode {  // to store data
private(set) var data: Int

// Reference to the next node
var next: DoublyNode?
// Reference to the previous node
var prev: DoublyNode?
init(data: Int) {
self.data = data
self.next = nil
self
.prev = nil
}
}
class DoublyLinkedList {  var head: DoublyNode
fileprivate var count: Int = 0
init(first: DoublyNode) {
add(element: first)
}
public func isEmpty() -> Bool {
return count == 0
}
public func size() -> Int {
return count
}
// adds an element at the beginning of the lis
public func add(element: DoublyNode) {
let node = element
// if list is empty, assign to head
if isEmpty() {
self.head = node
self.head?.next = nil
self
.head?.prev = nil
} else {
// head needs to be moved
let temporaryHead = self.head
self.head = node

node.next = temporaryHead
temporaryHead?.prev = node
self.head?.prev = nil
}
count += 1
}
}
// removes an element from the beginning of the list
public func remove() -> DoublyNode? {
if isEmpty() {
return nil
}
// remove the head
let item = self.head
self.head = self.head?.next
self.head?.prev = nil
item?.prev = nil
item?.next = nil

count -= 1
return item
}
// removes the node containing element as data
public func remove(_ element: Int) -> DoublyNode? {
if isEmpty() {
return nil
}

var temporaryNode = self.head

while temporaryNode != nil && temporaryNode?.data != element
{
temporaryNode = temporaryNode?.next
}
// found the element or nil
if temporaryNode == nil {
// we didn't find a node matching the data
return nil
}
// if the found node is head node, we move head
if temporaryNode?.data == self.head?.data {
return remove()
}
let previous = temporaryNode?.prev
let next = temporaryNode?.next
previous?.next = next
next?.prev = previous
count -= 1 temporaryNode?.prev = nil
temporaryNode?.next = nil
return temporaryNode}
extension DoublyLinkedList: CustomStringConvertible {
var description: String {
var string = ""
var node = head
while let n = node {
string += " \(n.data) "
node = node?.next
}

return string
}
}

let
doublyNode1 = DoublyNode(data: 1)
let doublyNode2 = DoublyNode(data: 2)
let doublyNode3 = DoublyNode(data: 3)
let doublyLinkedList = DoublyLinkedList(first: doublyNode1)print("List = \(doublyLinkedList)")
// "List = 1 \n"
doublyLinkedList.add(element: doublyNode2)doublyLinkedList.add(element: doublyNode3)
print(doublyLinkedList.size())
// 3
print(doublyLinkedList)
// "3 2 1 \n"
doublyLinkedList.remove()
print(doublyLinkedList.size()) // 2
print(doublyLinkedList) // "2 1 \n"
doublyLinkedList.remove(3) // doesn't exist
print(doublyLinkedList) // "2 1 \n"
doublyLinkedList.remove(1)
print(doublyLinkedList) // "2 \n"
doublyLinkedList.remove(2)
print(doublyLinkedList) // "\n"

Written by

Full Stack Developer, Engineer, Musician, Tech Curious, Tea Drinker, Sports lover

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store