Doubly Linked Lists and Circular Linked Lists - Eishaaya/GMRDataStructuresTest GitHub Wiki

What Makes It Doubly?

A doubly linked list improves upon the singly linked lists in a number of ways. First, as the name might suggest, nodes are connected in both directions, which means that the list could be traversed in the forward and backward directions. Second, since the previous node is now accessible, the tail node becomes useful. To delete the last node, for example, the list no longer needs to be traversed from the head. Finally, although possible with a singly linked list, adding a node at a random position can be done much more easily with a doubly linked list.

The node of a doubly linked list differs from that of a singly linked list only in that it also references a previous node:

class DoublyLinkedListNode<T>
{
    public DoublyLinkedListNode<T> Next { get; set; }
    public DoublyLinkedListNode<T> Previous { get; set; }

    public T Value { get; set; }

    public DoublyLinkedListNode(T value)
    {
        Value = value;
        Next = null;
        Previous = null;
    }
}

Becoming Circular

As you may have noticed, a tail node is not required for a doubly linked list.

However, one down side of the doubly linked list is that there is the efficiency problem of having to move to one side of the list during execution. For example, if the user was at the end of the list and needed to get to the head, one would need to for loop through the entire list to get to the other side, wasting an enormous amount of time.

This is solved by adding circularity to a linked list, meaning that the previous pointer of the head moves to the tail (last item in the list), and the next pointer on the tail moves to the head.

If you have a hard time visualizing what you are creating, see this link

Basic Set of Functions

void AddFirst(T value) Add a node to the front of the list.

void AddLast(T value) Add a node to the end of the list.

void AddBefore(Node node, T value) Add a node with the given value before the given node.

void AddAfter(Node node, T value) Add a node with the given value after the given node.

bool RemoveFirst() Remove a node from the front of the list.

bool RemoveLast() Remove a node from the end of the list.

bool Remove(T value) Remove the first node with the given value from the linked list.

bool IsEmpty() Determine if list is empty.

public int Count {get; private set;} Return the number of nodes in the list.

Implementation Guide

Adding to the end

If there isn't a head, make the nodeToInsert the head. If there is a head, add to the previous pointer of the head, properly effecting all connections to and from.

Add to the front

If there isn't a head, make the nodeToInsert the head. If there is a head, shift the current head to the nodeToInsert's next and place nodeToInsert as the Head.

Remove from front

If there is no head, then return false, otherwise remove the head and reconnect the next and previous items to each other if they exist.

Remove from end

If there is no head, return false, otherwise shift to head's previous pointer and remove item, reconnecting the associated links.

Assignments to be done with Circular-Doubly-Linked List

Easy:

  • Music Player
    • Use a circular doubly linked list to make a music player that can move to the next or previous.
  • Snake
    • Make a snake game with the new list you've created. Removing from the end of the list and adding to the front of the list should be much easier.
  • Sorted List
    • Create a SortedList class that inherits your DoublyLinkedList class and overrides the add function so that the add function adds the elements in sorted order.

Hard:

  • Programming a Caesar Cipher
    • See Caesar Cipher.
    • Allow string to be encrypted and decrypted accordingly using a circular doubly linked list.

References

<-- Previous | Next -->