W2295 Doubly-Linked Lists

Within these castle walls be forged Mavens of Computer Science ...

— Merlin, The Coder

Doubly-Linked List

Prerequisites

• W1301 Arrays
• W2294 Singly-Linked Lists

Introduction

A Linked Data Structure consists of a series of records, called nodes, linked to one another through a series of pointers. This arrangement contrasts with some other data structures, such as Arrays, where data are found through address calculations. You should already be familiar with the structure of a Singly-Linked List. This basic Linked Data Structure can evolve into the Doubly-Linked List for some added efficiencies.

Singly-Linked Lists

Singly-linked-list

As a refresher, the basic Singly-Linked-List is made with a series of Nodes, where each node is a structure consisting of the data (or some reference to the data) and a pointer to the Next Node. This pointer is often referred to asNext. A special pointer, called Head, points to the first node of the list. If a node doesn't have a subsequent node, its next pointer points to a special value called nil (or null in most languages outside of Swift). If a list is empty, the head itself will point to nil.

Recall that a Singly-Linked List is often used due to its ability to insert and delete any amount of data by simply redirecting a constant number of pointers. Also recall that Singly-Linked Lists were known for being difficult to traverse in the reverse direction since all the pointers point "forward". This is were Doubly-Linked Lists come in.

Doubly Linked List

A Doubly Linked List is similar to a Singly Linked List, but in addition to having a Next pointer, each node also has a second pointer, often referred to as prev (for previous) that points to the prior node. This allows one to traverse a Doubly-Linked List significantly more efficiently as well as more easily do operations such as deletion.

For example, imagine we want to implement a function where we want to delete a given Node, this is significantly more easy with a doubly-linked list as we are able to access the given Node's Prev and change the appropriate Next Pointer. However, this evolution of the Singly-Linked List does have some added complexity in that another pointer must now be handled.

Swift Implementation

For the following Swift Implementation of a Doubly-Linked List, we'll start using the code from our basic Singly-Linked List before adding several common functions to build a versatile structure. We'll want to start by implementing the Prev field onto our Node class.

public class Node {
  var value: String
  var next: Node?
  var prev: Node?
  init(value: String){
    self.value = value
  }
}

Make sure to keep this variable optional since the Head will have no prev in a strictly Doubly-Linked List. Now, we'll want to update our existing append function so that it sets up the prev pointers upon adding an entry to the end of the list. The new function would look like this.

public func append (value: String){
    let node = Node(value: value)
  
    if let lastNode = tail {
      node.prev = lastNode
      lastNode.next = node
    } 
    else {
      head = node
    }

    tail = node 
 }

}

Here, what's happening is we create a new node with the given value and if we can let the value of a constant lastNode = tail, then we can set lastNode's next to be our new node and our new node's prev to be what used to be the last node. Then, we set our Linked List's tail field to the new node that has been appended to the end. Just like that, all of the Nodes now have a Prev.

Now, let's update our remove function to be a little more practical, having it remove the given Node.

public func remove(index: Int) {
    let node = get(index: index)! //grab Node via index by using our custom get function
    let prev = node.prev!//set constant for node's prev
    let next = node.next!//set constant for node's next

    prev.next = next//circumvent given node by pointing prev to the given node's next and vice versa
    next.prev = prev
  }

Now, we're able to very easily append and delete items from our doubly-linked list. Let's try to now insert an item after a given node.

public func insert(value: String, after: Int?){
  let node = Node(value: value)
  
  if(after==nil){
    let firstNode = head
    
    node.prev = nil
    node.next = firstNode
    
    firstNode!.prev = node
    head = node
  }
    else{
    let afterNode = get(index: after!)
    let oldNext = afterNode!.next
    
    afterNode!.next = node
    node.prev = afterNode

    node.next = oldNext
    oldNext!.prev = node
  }

}

Here, what we're doing is creating our new node with the given value before checking to see if our after is nil which would we need to insert the Node at the head. If we have anything other than nil, we can get our afterNode and oldNext. All we have to do now is set our new Node to be after the after node and our newNodes's next to point to the oldNext so that the List remains intact.

By now, we have most of the functions in a Linked List that we would need. However, let's now implement two more functions, one that will tell us the size of the Linked List and another that will print each value. Both of these will require traversing through the Linked List which can be done via iteration.

 public func count() -> Int {
    var i = 0;
    var point = head
    while (point != nil){
      i+=1
      point = point!.next
    }
    return i;
  }

  public func getAll() -> String{
    var list = ""
    var i = 0
    var point = head
    while(point != nil){
      i+=1
      list += point!.value + ", "
      point = point!.next
    }
  return list
  }

These functions are mostly the same, they simply iterate through the List and return either the number of Nodes they found or a list of the Node's values. As an exercise, think of how you could make a function that both count() and getAll() could call so that there isn't redundant code.

Common Functions

Linked Lists have these common functions:

• isEmpty() returns true if the list is empty
• count() counts the nodes in the list
• getAll() returns the values of all nodes
• get(index) returns the node at a certain index
• append(value) appends a node to the end of the list
• insert(value, afterIndex) inserts a node immediately after the specified node's index; nil can be used to indicate the first node
• remove(index) deletes the specified node

Linked Lists vs Arrays

Category	Arrays	Linked Lists
Memory Allocation	When initially created	As the program executes
Memory Size	Fixed, often too large or too small	Can grow or shrink as needed
Memory Allocation Method	Must be contiguous	Can be freely located and relocated
Speed of Accessing Data	Nearly immediate, simple arithmetic. Strong locality of reference.	Requires traversing each node until target node is reached. Poor locality of reference.
Memory Consumption	Minimal overhead	Can have substantial overhead

Quiz

1 What is the pointer called that refers to the first Node of any given Linked List

	FirstNode
	Head
	Next
	First

2 What difficulties exist with Singly-Linked Lists that Doubly-Linked Lists solve

	Singly-Linked Lists could not insert or delete data efficiently
	Singly-Linked Lists could not change size during run time
	Singly-Linked Lists could not easily be traversed backward
	Singly-Linked Lists did not have efficient time complexity for searching or sorting

3 How do Doubly Linked Lists allow for backwards traversal?

	Inclusion of another pointer called the Prev which points to the previous Node
	The Ability to access the previous Node via an index
	Inclusion of another pointer called the Previous which points to the previous Node
	Inclusion of another pointer called the Head which points to the previous Node

4 What are the advantages and drawbacks of using Doubly-Linked Lists compared to Singly-Linked Lists

	Doubly Linked Lists allow for greater efficiencies with searching and sorting algorithms with no drawbacks
	Doubly Linked Lists allow for general efficiencies since the List is more accessible however now an additional pointer must be handled
	Doubly Linked Lists allow for greater efficiencies with only insertion methods since the list is more accessible
	Doubly Linked Lists allow for the List to be structured as a circle where the tail points to the head

Key Concepts

Key Concepts

• Doubly Linked Lists are a series of Nodes that point to each other one after the other just like Singly-Linked Lists
• A given Node has a value called Next, which is a reference to the next Node in the Linked List, but unlike Singly-Linked Lists, they also have a Prev which references the node prior to a given node
• Doubly Linked Lists can have slightly more complexity given that another pointer must be handled
• A Doubly Linked List can be significantly easier to work with given the ability to traverse backward and more easily access nodes for operations such as insertion and deletion

Exercises

Exercises

• Improve the above code by making a traverse() function which both the getAll() function and count() function can call
• Now, add onto this class a function for reverse traversing and use this to print all the Nodes in reverse order
• See if you can improve the insertion and deletion methods to allow for the insertion and deletion of multiple Nodes
• Finally, Implement some more complicated algorithms into the Doubly-Linked List. Start with a search function and then a Sort function for a more difficult challenge