# 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.

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  }}`
`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 integersvar singlyLinkedList = SinglyLinkedList<Int>()// add two elements to itsinglyLinkedList.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 elementsinglyLinkedList.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 listpublic 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 datapublic 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())// 3print(doublyLinkedList)// "3 2 1 \n"doublyLinkedList.remove()print(doublyLinkedList.size()) // 2print(doublyLinkedList) // "2 1 \n"doublyLinkedList.remove(3) // doesn't existprint(doublyLinkedList) // "2 1 \n"doublyLinkedList.remove(1)print(doublyLinkedList) // "2 \n"doublyLinkedList.remove(2)print(doublyLinkedList) // "\n"`

Written by