doublyLinkedList.md

Back

Doubly Linked List

A doubly linked list is the same as a singly linked list except each node also has a pointer to its previous node. This allows you to traverse the list in both directions. The first node is an object, and contains some data and a pointer to the next node, if there is no next node then it is just null. The reason why it is called a "doubly" linked list is because it can only be traversed in one direction. There are also doubly linked lists and circular linked lists that can be traversed in different ways. A linked list can contain any number of nodes and each node can contain any type of data. There is also usually a pointer to the tail of the list for easy access to it (Since if you didn't have the pointer you would need to traverse the whole list to get it every single time). A doubly linked list might look something like this in diagram:

{                                  {                                  {
  data: 'Some data 1'      / - - >   data: 'Some data 2'      / - - >   data: 'Some data 3'
  next: Pointer - - - - - /          next: Pointer - - - - - /          next: null
  previous: null < - - - - - - - - - previous: Pointer < - - - - - - - -previous: Pointer
}                                  }                                  }

You can create a new doubly linked list with the following code.

ES6:

import { DLL } from 'complete_data_structures';

const myDLL = new DLL()

CommonJS:

const { DLL } = require('complete_data_structures');

const myDLL = new DLL();

You can also supply parameters to create a linked list with preloaded items. You can create a linked list with one item in it like this:

const myDLL = new DLL('SomeVariable');

Or if you want to insert multiple items into your new linked list, you can do so by passing in an array of items:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

But what if you want to add an empty array? Well you can do this too by just supplying an empty array:

const myDLL = new DLL([]);

And finally if you want to add an array containing items as one item without it adding the contents of the array into individual items, you can set the third parameter to true, supplying a 0 for the second parameter:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3'], 0, true);

But why the third parameter? Well thats because the second parameter allows you to set a maximum size for the linked list so that it can't exceed a certain limit. If you supply a number greater than 0 it will then set the maximum size of the linked list to that number. If you supply a value of 0 or some other falsy value then the maximum size will be removed and the linked list will be free to grow as large as it wants. If you supply a number to set as the maximum size, if there are any values in the linked list that cause it to exceed the new maximum size then they will be removed automatically when you set the maximum size so be careful when doing this to a list that has items already in it. This also applies to when you try to initialize a linked list with items, if the size of the array you provided exceeds the maximum size your trying to set, it will not add all the items. If the linked list gets items cut off of it due to a maximum size being set, it cuts them from the tail of the linked list. Here is an example of initializing with a maximum size.

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3'], 8);

Here the maximum size is set to 8 so the linked list can never have more than 8 items in it at one time.

Methods:

All of the properties in the linked list are private and use getter and setter methods to provide access when needed. This provides encapsulation and makes sure that values can't accidently be set to the wrong thing (Imagine trying to set the maximum size to a Array!). Here are the methods that are supported by the linked list implementation:

getList

This method is simple, you call it and it returns the entire linked list. Will return null if the list is empty.
EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.getList();
// Expected Output: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: null
        }
    }
}

next

When you instantiate a new linked list it will start with a state set to the head node. The next method will move the pointer to the next node if there is one and return its data. This is how you traverse through the list. If there are no more nodes to traverse through, then it will keep returning the data value of the last node. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.next();
// Expected Output: 'SomeVar2'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: null
        }
    }
}

previous

This will allow you to traverse in the opposite direction. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.next();
// Expected Output: 'SomeVar2'
myStack.next();
// Expected Output: 'SomeVar3'
myStack.previous();
// Expected Output: 'SomeVar2'
myStack.previous();
// Expected Output: 'SomeVar1'
// Current List: {
    data: 'SomeVar1',
    previous: null,
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1'),
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2'),
            next: null
        }
    }
}

current

This will not move the pointer and just return the data from the node that the pointer is currently pointing to. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.current();
// Expected Output: 'SomeVar1'
myStack.next();
// Expected Output: 'SomeVar2'
myStack.current();
// Expected Output: 'SomeVar2'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: null
        }
    }
}

reset

This will reset the pointer back to the head node. This does not return anything. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.current();
// Expected Output: 'SomeVar1'
myStack.next();
// Expected Output: 'SomeVar2'
myStack.current();
// Expected Output: 'SomeVar2'
myStack.reset();
// Expected Output: undefined
myStack.current();
// Expected Output: 'SomeVar1'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: null
        }
    }
}

getTail

This will simply get the data from the tail node and return it. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.getTail();
// Expected Output: 'SomeVar3'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: null
        }
    }
}

size

This will just return the current size of the list. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.size();
// Expected Output: 3

addToTail

This will add an item to the tail of the list. You can also pass an array of items to add multiple items at once, or pass an empty array to add a node with an empty array, or set the second parameter to true if you want to add an array of items as a literal array of items. This works in the same way as when you instantiate a new linked list. This method does not return anything. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.getTail();
// Expected Output: 'SomeVar3'
myStack.addToTail('SomeVar4');
// Expected Output: undefined
myStack.getTail();
// Expected Output: 'SomeVar4'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: {
                data: 'SomeVar4',
                previous: Ref ('SomeVar3')
                next: null
            }
        }
    }
}

OR

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.getTail();
// Expected Output: 'SomeVar3'
myStack.addToTail(['SomeVar4', 'SomeVar5']);
// Expected Output: undefined
myStack.getTail();
// Expected Output: 'SomeVar5'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: {
                data: 'SomeVar4',
                previous: Ref ('SomeVar3')
                next: {
                    data: 'SomeVar5',
                    previous: Ref ('SomeVar4')
                    next: null
                }
            }
        }
    }
}

OR

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.getTail();
// Expected Output: 'SomeVar3'
myStack.addToTail([]);
// Expected Output: undefined
myStack.getTail();
// Expected Output: []
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: {
                data: [],
                previous: Ref ('SomeVar3')
                next: null
            }
        }
    }
}

OR

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.getTail();
// Expected Output: 'SomeVar3'
myStack.addToTail(['SomeVar4', 'SomeVar5'], true);
// Expected Output: undefined
myStack.getTail();
// Expected Output: ['SomeVar4', 'SomeVar5']
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar3',
            previous: Ref ('SomeVar2')
            next: {
                data: ['SomeVar4', 'SomeVar5'],
                previous: Ref ('SomeVar3')
                next: null
            }
        }
    }
}

addToHead

This method behaves exactly like the addToTail method except it adds items to the head of the list instead of the tail. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myStack.addToHead('SomeVar4');
// Expected Output: undefined
// Current List: {
    data: 'SomeVar4',
    previous: null
    next: {
        data: 'SomeVar1',
        previous: Ref ('SomeVar4')
        next: {
            data: 'SomeVar2',
            previous: Ref ('SomeVar1')
            next: {
                data: 'SomeVar3',
                previous: Ref ('SomeVar2')
                next: null
            }
        }
    }
}

getMax

Gets the maximum size of the list if there is one. Will return null if no maximum size is set. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3'], 4);

myDLL.getMax()
// Expected Output: 4

setMax

This will set the maximum size of the list. This will also remove any items from the tail of the list that go over the new maximum size you set. This method does not return anything. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.getMax()
// Expected Output: null
myDLL.setMax(4)
// Expected Output: undefined
myDLL.getMax()
// Expected Output: 4

isEmpty

This will return whether or not the list is empty. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.isEmpty()
// Expected Output: false

OR

const myDLL = new DLL();

myDLL.isEmpty()
// Expected Output: true

isFull

This will check to see if the list is at the maximum size if one is set and return whether or not its full. If no maximum size is set it returns null. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.isFull()
// Expected Output: null

OR

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3'], 3);

myDLL.isFull()
// Expected Output: true

OR

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3'], 4);

myDLL.isFull()
// Expected Output: false

contains

This will search through the list and find all of the nodes with data that match a given parameter. If nothing is found it will return null. It will return an array with all of the index numbers of each node found to have a match or if only one match was found it will return that index as a number. You can supply a boolean for the second parameter to tell it to do an extensive comparison. This will cause it to search for items by comparing the json string of each items data. This of course is a bit slower so if you don't have any array's, object's, or date's in your linked list then it's better to not have this parameter set as it will slow down the search a bit. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3', 'SomeVar3']);

myDLL.contains('SomeVar2');
// Expected Output: 1
myDLL.contains('SomeVar7');
// Expected Output: null
myDLL.contains('SomeVar3');
// Expected Output: [2, 3]

getAt

This will get the data from the node at the index number passed to it. Will return null if the number passed is negative or out of range. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.getAt(1);
// Expected Output: 'SomeVar2'
myDLL.getAt(7);
// Expected Output: null
myDLL.getAt(-1);
// Expected Output: null

reverse

This will reverse the linked lists order. This does not return anything. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.reverse()
// Expected Output: undefined
// Current List: {
    data: 'SomeVar3',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar3')
        next: {
            data: 'SomeVar1',
            previous: Ref ('SomeVar2')
            next: null
        }
    }
}

insertAt

This will insert a node with data at a specific index. This does not return anything. The first parameter is the index you want to place the node at and the second parameter is data. You can add multiple items in the same way as addToHead and addToTail. The third parameter will tell the method to input your array as a literal array. You can also insert into the head or tail with this method. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.insertAt(1, 'SomeVar0')
// Expected Output: undefined
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar0',
        previous: Ref ('SomeVar1')
        next: {
            data: 'SomeVar2',
            previous: Ref ('SomeVar0')
            next: {
                data: 'SomeVar3',
                previous: Ref ('SomeVar2')
                next: null
            }
        }
    }
}

removeAt

This will remove a node at a specific index and return the data that was in that node. It will return null if a negative number or an out of range number is supplied. You can also remove the head or tail with this method. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.removeAt(1)
// Expected Output: 'SomeVar2'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar3',
        previous: Ref ('SomeVar1')
        next: null
    }
}

removeTail

This will remove the tail node from the list and return the data that was in that node. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.removeTail()
// Expected Output: 'SomeVar3'
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar2',
        previous: Ref ('SomeVar1')
        next: null
    }
}

removeHead

This will remove the head node from the list and return the data that was in that node. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3']);

myDLL.removeHead()
// Expected Output: 'SomeVar1'
// Current List: {
    data: 'SomeVar2',
    previous: null
    next: {
        data: 'SomeVar3',
        previous: Ref ('SomeVar2')
        next: null
    }
}

removeData

This will remove all the nodes that match the data provided. You can use extensive comparison with this method just like you can with contains by setting the second parameter to true. The return value is the number of nodes that were removed. EXAMPLE:

const myDLL = new DLL(['SomeVar1', 'SomeVar2', 'SomeVar3', 'SomeVar2', 'SomeVar2']);

myDLL.removeData('SomeVar2')
// Expected Output: 3
// Current List: {
    data: 'SomeVar1',
    previous: null
    next: {
        data: 'SomeVar3',
        previous: Ref ('SomeVar1')
        next: null
    }
}