-
Notifications
You must be signed in to change notification settings - Fork 98
Double Linked List
In computer science, a doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node. The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly-linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
Wikipedia
var listA = new DoubleLinkedList(); //an empty list
var listB = new DoubleLinkedList(0, 1, 2, 3); //listB contains 0, 1, 2, 3
var listC = new DoubleLinkedList(Range(0, 3)); //listC contains 0, 1, 2, 3 This method returns an iterator for scanning the list. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.
var list= new DoubleLinkedList();
var it = list.getIterator();
for(it.first(); !it.isDone(); it.next()) {
var item = it.getItem();
//do something
}The iterator starts from the head of the list.
This method push the item at the head of the list. The item could be whatever you want.
var list = new DoubleLinkedList();
list.pushFront(4); //list contains 4
list.pushFront(2); //list contains 2, 4This method push the item at the tail of the list. The item could be whatever you want.
var list = new DoubleLinkedList();
list.pushBack(4); //list contains 4
list.pushBack(2); //list contains 4, 2This method remove the item at the head of the list. The item is returned.
var list = new DoubleLinkedList(4, 2); //list contains 4, 2
list.popFront(); //4 and list contains 2This method remove the item at the tail of the list. The item is returned.
var list = new DoubleLinkedList(4, 2); //list contains 4, 2
list.popBack(); //2 and list contains 4This method removes the first times items at the head of the list. The items are returned as an array.
var list = new DoubleLinkedList(6, 8, 4, 2); //list contains 6, 8, 4, 2
list.multiPopFront(2); //[6, 8] and list contains 4, 2This method removes the last times items at the tail of the list. The items are returned as an array.
var list = new DoubleLinkedList(6, 8, 4, 2); //list contains 6, 8, 4, 2
list.multiPopBack(2); //[2, 4] and list contains 6, 8This method takes the item at the head of the list without removing it.
var list = new DoubleLinkedList(6, 8, 4, 2); //list contains 6, 8, 4, 2
list .peek(); //6 and list contains 6, 8, 4, 2This method add the item at the position index of the list. The item could be whatever you want. If the index is lower than 0, the item won't be added. Instead, if the index is over the length of the list, will be added empty nodes until the position will reached.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.addAt(2, 9); //list contains 6, 8, 9, 4, 2
list.addAt(-1, 5); //list contains 6, 8, 9, 4, 2
list.addAt(7, 1); //list contains 6, 8, 9, 4, 2, empty, empty, 1This method removes the item stored at the position index of the list. The item is not returned.
var list = new DoubleLinkedList(6, 8, 4, 2, 7); //list contains 6, 8, 4, 2, 7
list.removeAt(1); //list contains 6, 4, 2, 7
list.removeAt(2); //list contains 6, 4, 7This method removes the first item that satisfy the condition represented by the callback function. The item is not returned. The callback could be omitted. In this case the method checks if the item there is in the list.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.remove(8); //list contains 6, 4, 2If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var list = new DoubleLinkedList(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.remove(null, callback); //list contains 6, 8, 2In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.remove(null, callback); //list contains itemAThis method removes all the items that satisfy the condition represented by the callback function. The items are not returned. The callback could be omitted. In this case the method checks if the item there is in the list.
var list = new DoubleLinkedList(6, 8, 4, 8, 2);
list.removeAll(8); //list contains 6, 4, 2If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var list = new DoubleLinkedList(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.removeAll(null, callback); //list contains 6, 8In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var itemC = {parent: itemA; key: 2};
var list = new DoubleLinkedList(itemA, itemB, itemC);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.removeAll(null, callback); //list contains itemAThis method removes the item stored from the position from to the position to of the list. The items are returned.
var list = new DoubleLinkedList(6, 8, 4, 2, 7);
list.removeSegment(1, 3); //[8, 4, 2] and list contains 6, 7This method modifies the item stored at the position index of the list.
var list = new DoubleLinkedList(6, 8, 4, 2, 7);
list.modifyAt(1, 6); //list contains 6, 6, 4, 2, 7This method empty the list.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.clear(); //the list is emptyThis method checks if the list contains an item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method checks if the item is simply contained in the list.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.contains(4); //true
list.contains(1); //falseIf you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var list = new DoubleLinkedList(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.contains(null, callback); //trueIn this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.contains(null, callback); //trueThis method execute the callback function for each item stored in the list. The callback must accept the item the iteration is working on. The callback must also return a value to assign to the item.
var list = new DoubleLinkedList(6, 8, 4, 2);
var callback = function(item) { //this function returns the square for each item
return item * item;
};
list.execute(callback); //list contains 36, 64, 16, 4In this example we deal with more complex items.
var list = new DoubleLinkedList(0, 1);
var callback = function(item) { //this function encapsulate each item into an object
return {x: item, y: item + 2};
};
list.execute(callback); //list contains {x: 0, y: 2}, {x: 1, y: 3}This method returns the node at position index of the list.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.getNode(0); //{item: 0, next: node}
list.getNode(1); //{item: 1, next: node}This method returns the item at position index of the list.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.getItem(0); //6
list.getItem(1); //8This method returns an array that contains the items of the list.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.toArray(); //[6, 8, 4, 2]This method fill the list from the array.
var list = new DoubleLinkedList();
list.fromArray([6, 8, 4, 2]); //list contains 6, 8, 4, 2This method returns the length of the list so the number of items stored.
var list = new DoubleLinkedList();
list.getLength() //0 - the list is empty
list.pushBack(0);
list.pushBack(1);
list.pushBack(2);
list.getLength(); //3This method checks if the list is empty or not.
var list = new DoubleLinkedList();
list.isEmpty(); //true
list.pushBack(6);
list.pushBack(8);
list.pushBack(2);
list.isEmpty(); //falseThis method returns all the items that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on.
var list = new DoubleLinkedList(6, 8, 4, 2);
var callback = function(item) { //this function checks if the item is lower than 4 or greater than 6
return item < 4 || item > 6;
};
list.filter(callback); //[2, 8];In this example we deal with more complex items.
var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var list = new DoubleLinkedList(itemA, itemB, itemC, itemD);
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
while(item.parent || item === itemA)
item = item.parent;
return item === itemA;
};
list.filter(callback); //[itemC, itemB, itemA]This method returns the first position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the first position where the item is stored. If nothing has been found, the method returns -1.
var list = new DoubleLinkedList(6, 8, 4, 2);
list.indexOf(4); //2
list.indexOf(5); //-1If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var list = new DoubleLinkedList(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.indexOf(null, callback); //2In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.indexOf(null, callback); //1This method returns the last position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the last position where the item is stored. If nothing has been found, the method returns -1.
var list = new DoubleLinkedList(6, 2, 4, 8, 6, 8, 4, 2);
list.lastIndexOf(4); //6
list.lastIndexOf(5); //-1If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var list = new DoubleLinkedList(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.lastIndexOf(null, callback); //4In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.lastIndexOf(null, callback); //2This method returns all the positions of the items that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns all the positions where the item is stored.
var list = new DoubleLinkedList(6, 2, 4, 8, 6, 8, 4, 2);
list.allIndexesOf(4); //[2, 6]
list.allIndexesOf(5); //[]If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.
var list = new DoubleLinkedList(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.allIndexesOf(null, callback); //[1, 2, 6, 7]In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.allIndexesOf(null, callback); //[1, 2]This method sorts the list taking advantage of the workers of JavaScript. Unfortunately, it's very instable due to the various implementation of that in different browsers. In particular there's a maximum number of worker that could be active and for many browser this number is very low causing the crash of the page. So it's dissuaded from a serious use but this is one of the possible use of the JavaScript's workers. If you are interested in, you could read the code to understand how it works. In this case, the use of the workers is more similar than an actor rather than a common thread.
var list = new DoubleLinkedList(6, 3, 2, 7, 4, 8);
list.parallelSort(); //list contains 2, 3, 4, 6, 7, 8This method sorts the list using the callback in order to get the right element to compare. The callback could be omitted.
var list = new DoubleLinkedList(6, 3, 2, 7, 4, 8);
list.sort(); //list contains 2, 3, 4, 6, 7, 8If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on.
var list = new DoubleLinkedList(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function return the opposite item
return -item;
};
list.sort(callback); //list contains 8, 7, 6, 4, 3, 2In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB, itemB);
var callback = function(item) { //this function return the key of the item
return item.key;
};
list.sort(callback); //list contains itemB, itemB, itemAThis method reverses the items stored in the list
var list = new DoubleLinkedList(6, 3, 2, 7, 4, 8);
list.reverse(); //list contains 8, 4, 7, 2, 3, 6This method returns the number of the items that satisfy the condition represented by the callback function.
var list = new DoubleLinkedList(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
return item < 5;
};
list.count(callback); //4In this example we deal with more complex items.
var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var list = new DoubleLinkedList(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA
return item.parent === itemA;
};
list.count(callback); //2This method append the list at the end of this list.
var listA = new DoubleLinkedList(6, 8, 4, 2);
var listB = new DoubleLinkedList(7, 8, 5, 3);
listA.join(listB); //listA contains 6, 8, 4, 2, 7, 8, 5, 3This method divides the list at the position index and return a list containing the items cut from the list.
var listA = new DoubleLinkedList(6, 8, 4, 2);
var listB = listA.divide(2); //listB contains 4, 2 and listA contains 6, 8This method divides the list into an array of lists each one of a maximum length equals to the parameter size.
var list = new DoubleLinkedList(6, 8, 4, 2, 5, 7, 9, 1);
var lists = list.split(3); //lists contains 3 lists
lists[0]; //contains 6, 8, 4
lists[1]; //contains 2, 5, 7
lists[2]; //contains 9, 1This method returns a clone of the list. The items are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old list. This problem there is not if items are not object.
var list = new DoubleLinkedList(6, 8, 4, 2);
var clone = list.clone(); //clone contains 6, 8, 4, 2This method returns a clone of the list containing only one copy of the same item. The items are cloned only if there's a method cloneDistinct() to invoke or at least a method clone(), otherwise they will be shared with the old list. This problem there is not if items are not object.
var list = new DoubleLinkedList(2, 8, 4, 6, 8, 4, 2, 6);
var clone = list.cloneDistinct(); //clone contains 2, 8, 4, 6m: the number of distinct elements stored in the list. The time required depends strongly from the number of items duplicated. If the number of items duplicated is very high, then m tend to be near 1 (when the list contains only one distinct item) so complexity will be O(n). If the number of items duplicated is very low, then m tend to be near n (when the list doesn't contain any duplicated items) so complexity will be O(n2).