W2294 Singly-Linked Lists

From Coder Merlin
Within these castle walls be forged Mavens of Computer Science ...
— Merlin, The Coder

Overview[edit]

In Computer Science, it is essential that you are familiar with a Linked List data structure. A Singly Linked List is the most simple form of a Linked List and acts as a linear data structure. Being a linear data structure means Linked Lists hold some data in a linear fashion--a simple list where each item is organized one after the other (for example, a list of users for an application).

Often, this data structure is compared to its simpler alternative: Arrays. In the following, we'll explore the features of Linked Lists, their uses, how they're programmed. Throughout, we will contrast them with other data structures, namely Arrays and Dynamic Arrays

Structure[edit]

The structure of a Linked List is perhaps the most important of its features. Simply, a Linked List contains two parts for every element that needs to be stored. There is the Node and the Next. The Node is what stores the data and the Next (also referred to as a pointer) points to the next Node in the sequence. Because of this, a Singly Linked List is simply a series of Nodes that contain data, each of which has a Next that refers to the next Node in the sequence.

This begs the question, what does the last Node point to? In the case of a Singly Linked List, the final Node contains null or its equivalent in the language. For the Swift programming language, this would the value nil.

Additionally, the beginning of a Linked List is called the head. It's important to understand the head is not the first element being stored, rather it is the reference to the first Node. It's essentially a Next value that refers to the first Node, and if the Head returns null or its equivalent, that indicates the Linked List is empty.

For further clarification, see the diagram below.

Diagram[edit]

Structure of a Singly Linked List

Coding a Linked List[edit]

To start coding a Linked List, first declare a Node class that describes the Node's value and its Next. Then a Linked List class will be made to handle the functions we'd like to use.

 
public class Node {
  var value: String
  var next: Node? //use ? operator so next can equal nil at the end
  init(value: String){
    self.value = value
  }
}

For convenience, we'll include some basic functions in our Linked List class to get the head and tails of the Linked List.

 
public class LinkedList {
  
  private var head: Node? 
  private var tail: Node?
  
  public var firstNode: Node? {
    return head
  }

  public var lastNode: Node? {
    return tail
  }
}

Then, we'll make some basic functions in the LinkedList class, starting with append (adding an item at the end)

 
 public func append (value: String){
    let node = Node(value: value)
  
    if let lastNode = tail {
      lastNode.next = node //has the current lastNode point to the new node
    } 
    else {
      head = node //populates head if list is empty
    }

    tail = node //configures the field of tail in the Linked List class to node
 }

Now, we can make a function to remove a Node. The functionality for this will be difficult, however using Singly Linked Lists, you see, it is very difficult to back-track with a strict Singly Linked list, which is why Doubly Linked Lists are typically used when back tracking is needed. Nevertheless, we will implement the function with the precondition that the item following the given Node will be removed.

 
public func remove(node: Node) -> String {
    let next = node.next
    if next == nil{} // do nothing if the last node was given
    else if let secondNext = next!.next{
      node.next = secondNext              
    }
    return node.value
  }

Finally, let's attempt to return a given Node at an index. For these sorts of use cases, an Array will typically be better, but the following will accomplish this.

 
public func get(index: Int) -> Node? {
  if index >= 0 {
    var node = head
    var i = index
    while node != nil {
      if i == 0 { return node }
      i -= 1
      node = node!.next
    }
  }
  return nil
}

Finally, let's put this all together with a demo using all the methods we made. In addition, we'll want to make a simple String Convertible so we can properly print out our Linked List.

 

extension LinkedList: CustomStringConvertible {
  public var description: String {
    var text = "["
    var node = head
    while node != nil {
      text += "\(node!.value)"
      node = node!.next
      if node != nil { text += ", " }
    }
    return text + "]"
  }
}

var carList = LinkedList()

carList.append(value:"J-150")
carList.append(value:"Civil")
carList.append(value:"Golderado")
carList.append(value:"Goat")
carList.append(value:"Thunder J-150")
carList.append(value:"Nikola Model Y")
carList.remove(node: carList.get(index:0)!)

print(carList)

Implications[edit]

Now with understanding the key idea behind Singly Linked Lists and some experience coding one, we need to understand the implications this structure of data storage. Specifically, we'll look at its implications on Time Complexity and Space Complexity while describing the Singly Linked Lists strengths as compared to the data structure of Arrays.

First, a clarification on Time Complexity and Space Complexity. These terms refer to performing any code where Time Complexity involves the time it takes to perform a certain program, and Space Complexity refers to the memory that must be allocated for the same program. These two metrics are important to look at when considering a program's performance.

Space Complexity[edit]

Let's take a look at the Space Complexity of a Singly Linked List. A Singly Linked List is said to have linear Space Complexity, which means that for n elements that must be stored, the space that must be allocated will scale by n. More specifically, 2 spaces in memory must be allocated for each element that is meant to be stored. This is because for each element, there is a Node that stores the actual data and a Next that points to the data.

In this regard, Arrays are more efficient because they require only one area of memory allocation for each element that must be stored. This is because Arrays do not have any pointers or Nexts.

Additionally, the memory allocation of Linked Lists are also a factor compared to Arrays. Arrays have memory allocated such that each element of data is "next" to each other, but Linked Lists have their data elements stored arbitrarily in memory meaning the data can be stored in a very disconnected fashion and the CPU could be subject to weaker performance. The following image represents the likeness of a Linked List's relatively scattered memory.

A Linked List's memory can be scattered


Time Complexity[edit]

However, in terms of Time Complexity, Linked Lists have several unique advantages when it comes to insertion and deletion of elements. Both of these operations are said to take constant time, meaning it would take the same time for the computer to execute the operation regardless of the amount of elements that need to be inserted or deleted.

To understand why this is, recall the structure of a Linked List. Because it's nothing more than Nodes containing data to point to each other, all that needs to be done to insert new Nodes is change two pointers.

Take the below diagram. We have the primary Linked List and below that is a secondary Linked List that we wish to insert into the middle of the primary using some code.

Condition before insertion

All we need to do is traverse to the middle Node and set its Next value to be the Node we wish to add, then simply set the Next of that Node to point back to the Primary Linked List.

Notice the order of the List is now 1, 4, 2, 3

The same approach can be used for deletion, but instead the idea is to circumvent a Node or series of Nodes by having the appropriate Next values around the given Nodes.

With this understanding, try to go back to the code examples and understand where these shifts were made to allow insertion and deletion of Nodes.

Compared to Arrays, Linked List are vastly more flexible in terms of deletion and insertion. In most languages, Arrays cannot be changed, meaning a new Array would have to be made for every insertion or deletion of an element. The time required for this would be linear, scaling for every element that must be added. Linked Lists are significantly superior in this regard.

Using pointers does make it so the operations of searching and sorting are somewhat more difficult. As mentioned in the coding example, back-tracking with a strictly singular Linked-List is rather difficult. This is because to traverse a Singly Linked List, you must go through each pointer, restricting time for Searches and Sorts to linear time and making forward the only way to traverse through the list. In a sense, Singly Linked Lists can be searched only sequentially because they have no indexes to reference for binary searches or otherwise. In this regard, arrays provide a better performance.

Usages[edit]

Now that you know this data structure on a fairly deep level, we'll look at the uses of Singly Linked Lists. Recall that Linked Lists shine best when it comes to insertions and deletions while being sub-optimal for searching and sorting.

Therefore, the optimal uses of Singly Linked Lists are instances where times for insertion and deletion are critical, where the number of elements that need to be stored is not known up front, and where access to arbitrary values in the list is not needed.

Many examples of Singly Linked Lists, in fact, are other more complicated data structures. For example, a Stack is made using Singly Linked Lists because insertion and deletion of elements is a regular operation that must be done and not finding random elements within the Stack. The Stack data structure is used for many low-level operations and handling functions, expressions, algorithms, memory, etc.

Indeed, Singly Linked Lists are behind a great many of the common features of Computer Science. Their simple structure allows them to be used to be used in both niche and broad applications.

Quiz[edit]

1 Which of these is the best definition of a singly linked list?

An unchangeable series of data stored linearly, one after the other
A series of values called Nodes where each node points to the next and previous nodes
A series of values called Nodes where each node points to the next node
A series of data that follows the First-in last-out principle

2 What is the name of the value used to reference the node after a given node?

an After
a Next
a Prev
a Pointer

3 Why do Linked Lists have greater space complexity than Arrays?

Because Linked Lists require both a data value and a Next to reference the next Node
Because Nodes are stored randomly in memory
Linked Lists use the exact same space as an Array counter part
Linked Lists can be changed while Arrays can not

4 Why do Linked Lists have constant time complexity for insertion and deletion operations?

Because Nodes can be adjusted by changing their pointers one by one for each Node that needs to be changed
Each Node needs to be sequentially searched through
Linked Lists have logarithmic time complexity for insertion and deletion operations
Any series of Nodes can be inserted or deleted by changing the same number of pointers, regardless of how many Nodes need to be changed

5 Why do Linked Lists have linear time complexity for Searching and Sorting operations?

Searching and sorting algorithms cannot be done using Linked Lists
Each Node needs to be sequentially searched through, and no indexes are available for advanced sorting algorithms
Linked Lists can have logarithmic time complexity for searching and sorting operations by adjusting pointers
Because Singly Linked Lists lack a reference to prior Nodes

6 In which scenario is a Singly Linked List better to use than an Array?

Random access to data is needed in conjunction with Search algorithms
A known set of data needs to be mutated, requiring iterations back and forth
An unknown amount of data needs to be stored linearly

7 In which scenario is an Array better to use than a Singly Linked List?

Large amounts of data need to be sorted before various processes
Data needs to be simulated in the form of a Stack that follows the Fist-In, Last-out Principle
Random access to data is not needed, only values such as the front and back of a list

8 True or False: Singly Linked Lists have references to Prior Nodes.

True
False

9 True or False: Stacks are used to make Linked Lists

True
False

10 True or False: The Head of a Linked List refers to the first Node

True
False


Key Concepts[edit]

Key ConceptsKeyConceptsIcon.png
  • Structure of a Linked List
    • Singly Linked Lists are a series of Nodes that point to each other one after the other
    • A given Node has a value called Next, which is a reference to the next Node in the Linked List
  • Efficiency
    • Singly Linked Lists are very efficient at insertion and deletion because the time required for these operations is the same regardless of how much data needs to be inserted or deleted
    • Singly Linked Lists are generally less space efficient than Arrays
    • Singly Linked Lists are generally less time efficient than Arrays when it comes to sequencing and sorting
  • Usages
    • Singly Linked Lists are best for applications with many insertions and deletions
    • Singly Linked Lists are used to create data structures such as Stacks and other low-level operations