Singly and Doubly Linked Lists

     There are three types of linked lists: singly, doubly and circular.  Today I will be talking about singly and doubly linked lists. Linked lists are a type of data structure that helps us store data that are made up of nodes. Linked lists are linear and are an alternative to using arrays. The data is stored in a non-contigious way, which means the data is storad randomly and not in a straigh line. Unlike arrays, the size of a linked list is not fixed. The size/length of the list can increase or decrease on demand. One down size to a linked list is that it does not allow direct access to individual elements(nodes) like arrays do.

Singly Linked Lists:

 Let's start with singly linked lists.  A singly linked list has nodes that contain a piece of data and a pointer that references the next node in the list.  When searching for data, you have to start at the head, which will point to the first node, which then only points to the following node and so on. It is similar to looping through an unsorted array.  The time complexity of a singly linked list the most efficiant but does not take up much memory. Singly linked lists are mainly used to implement stacks.

Let's take a look at the ES6 setup for a singly linked list:

class Node{
    constructor(data, next = null){
        this.data = data,
        this.next = next
    }
}

Doubly Linked Lists:

   Doubly linked lists also contain nodes. What makes Doubly linked lists different from singly linked lists is that in addition to each node holding data and a pointer that points to the next node, it also has a pointer that points to the previous node as well. With a singly linked list you can only traverse the list by starting at the head, but with the doubly linked list you can start at either the head or the tail. This makes it a little bit more efficiant to traverse through than a singly linked list.  However, due to the extra pointer, doubly linked lists take up more memory. Doubly linked lists can be used to make stacks, heeps and binary search trees

Here is the ES6 set up for a doubly linked list:

class DoublyLinkedListNode {
   constructor(data) {
       this.data = data;
       this.next = null;
       this.previous = null;
   }
}

Here is a look at the time complexity of linked lists:

Linked lists are good when needing to insert or delete data. Worse-case Scenario time complexity for inserting or deleting in linked lists is O(1) which is constant. Unfortunately when accessing or searching, the time complexity is O(n)(linear) which means it willtakelonger to access or search.

In conclusion, when trying to decide which data structure to use for your project, think about what your project will be doing and what is most important to you.  Are you going to be constantly adding and deleting data or are you mostly only going to be accessing/looking up data?  What is more important to you: effeciancy or memory.  Both singly and doubly linked lists are handy but depending on your needs you may chooseoneover the other.