# W2294 Singly-Linked Lists

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

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

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

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.

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]

## Key Concepts[edit]

- 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