- Notifications
You must be signed in to change notification settings - Fork55
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
varlistA=newDoubleLinkedList();//an empty listvarlistB=newDoubleLinkedList(0,1,2,3);//listB contains 0, 1, 2, 3varlistC=newDoubleLinkedList(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.
varlist=newDoubleLinkedList();varit=list.getIterator();for(it.first();!it.isDone();it.next()){varitem=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.
varlist=newDoubleLinkedList();list.pushFront(4);//list contains 4list.pushFront(2);//list contains 2, 4
This method push the item at the tail of the list. The item could be whatever you want.
varlist=newDoubleLinkedList();list.pushBack(4);//list contains 4list.pushBack(2);//list contains 4, 2
This method remove the item at the head of the list. The item is returned.
varlist=newDoubleLinkedList(4,2);//list contains 4, 2list.popFront();//4 and list contains 2
This method remove the item at the tail of the list. The item is returned.
varlist=newDoubleLinkedList(4,2);//list contains 4, 2list.popBack();//2 and list contains 4
This method removes the first times items at the head of the list. The items are returned as an array.
varlist=newDoubleLinkedList(6,8,4,2);//list contains 6, 8, 4, 2list.multiPopFront(2);//[6, 8] and list contains 4, 2
This method removes the last times items at the tail of the list. The items are returned as an array.
varlist=newDoubleLinkedList(6,8,4,2);//list contains 6, 8, 4, 2list.multiPopBack(2);//[2, 4] and list contains 6, 8
This method takes the item at the head of the list without removing it.
varlist=newDoubleLinkedList(6,8,4,2);//list contains 6, 8, 4, 2list.peek();//6 and list contains 6, 8, 4, 2
This 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.
varlist=newDoubleLinkedList(6,8,4,2);list.addAt(2,9);//list contains 6, 8, 9, 4, 2list.addAt(-1,5);//list contains 6, 8, 9, 4, 2list.addAt(7,1);//list contains 6, 8, 9, 4, 2, empty, empty, 1
This method removes the item stored at the position index of the list. The item is not returned.
varlist=newDoubleLinkedList(6,8,4,2,7);//list contains 6, 8, 4, 2, 7list.removeAt(1);//list contains 6, 4, 2, 7list.removeAt(2);//list contains 6, 4, 7
This 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.
varlist=newDoubleLinkedList(6,8,4,2);list.remove(8);//list contains 6, 4, 2
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.
varlist=newDoubleLinkedList(6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.remove(null,callback);//list contains 6, 8, 2
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};list.remove(null,callback);//list contains itemA
This 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.
varlist=newDoubleLinkedList(6,8,4,8,2);list.removeAll(8);//list contains 6, 4, 2
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.
varlist=newDoubleLinkedList(6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.removeAll(null,callback);//list contains 6, 8
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varitemC={parent:itemA; key:2};varlist=newDoubleLinkedList(itemA,itemB,itemC);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};list.removeAll(null,callback);//list contains itemA
This method removes the item stored from the position from to the position to of the list. The items are returned.
varlist=newDoubleLinkedList(6,8,4,2,7);list.removeSegment(1,3);//[8, 4, 2] and list contains 6, 7
This method modifies the item stored at the position index of the list.
varlist=newDoubleLinkedList(6,8,4,2,7);list.modifyAt(1,6);//list contains 6, 6, 4, 2, 7
This method empty the list.
varlist=newDoubleLinkedList(6,8,4,2);list.clear();//the list is empty
This 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.
varlist=newDoubleLinkedList(6,8,4,2);list.contains(4);//truelist.contains(1);//false
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.
varlist=newDoubleLinkedList(6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.contains(null,callback);//true
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};list.contains(null,callback);//true
This 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.
varlist=newDoubleLinkedList(6,8,4,2);varcallback=function(item){//this function returns the square for each itemreturnitem*item;};list.execute(callback);//list contains 36, 64, 16, 4
In this example we deal with more complex items.
varlist=newDoubleLinkedList(0,1);varcallback=function(item){//this function encapsulate each item into an objectreturn{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.
varlist=newDoubleLinkedList(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.
varlist=newDoubleLinkedList(6,8,4,2);list.getItem(0);//6list.getItem(1);//8
This method returns an array that contains the items of the list.
varlist=newDoubleLinkedList(6,8,4,2);list.toArray();//[6, 8, 4, 2]
This method fill the list from the array.
varlist=newDoubleLinkedList();list.fromArray([6,8,4,2]);//list contains 6, 8, 4, 2
This method returns the length of the list so the number of items stored.
varlist=newDoubleLinkedList();list.getLength()//0 - the list is emptylist.pushBack(0);list.pushBack(1);list.pushBack(2);list.getLength();//3
This method checks if the list is empty or not.
varlist=newDoubleLinkedList();list.isEmpty();//truelist.pushBack(6);list.pushBack(8);list.pushBack(2);list.isEmpty();//false
This method returns all the items that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on.
varlist=newDoubleLinkedList(6,8,4,2);varcallback=function(item){//this function checks if the item is lower than 4 or greater than 6returnitem<4||item>6;};list.filter(callback);//[2, 8];
In this example we deal with more complex items.
varitemA={parent:null,item:0};varitemB={parent:itemA,item:1};varitemC={parent:itemB,item:2};varitemD={parent:null,item:3};varlist=newDoubleLinkedList(itemA,itemB,itemC,itemD);varcallback=function(item){//this function checks if itemA is in the same hierarchy of the itemwhile(item.parent||item===itemA)item=item.parent;returnitem===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.
varlist=newDoubleLinkedList(6,8,4,2);list.indexOf(4);//2list.indexOf(5);//-1
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.
varlist=newDoubleLinkedList(6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.indexOf(null,callback);//2
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};list.indexOf(null,callback);//1
This 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.
varlist=newDoubleLinkedList(6,2,4,8,6,8,4,2);list.lastIndexOf(4);//6list.lastIndexOf(5);//-1
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.
varlist=newDoubleLinkedList(6,2,4,8,6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.lastIndexOf(null,callback);//4
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};list.lastIndexOf(null,callback);//2
This 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.
varlist=newDoubleLinkedList(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.
varlist=newDoubleLinkedList(6,2,4,8,6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.allIndexesOf(null,callback);//[1, 2, 6, 7]
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.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 anactor rather than a commonthread.
varlist=newDoubleLinkedList(6,3,2,7,4,8);list.parallelSort();//list contains 2, 3, 4, 6, 7, 8
This method sorts the list using the callback in order to get the right element to compare. The callback could be omitted.
varlist=newDoubleLinkedList(6,3,2,7,4,8);list.sort();//list contains 2, 3, 4, 6, 7, 8
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.
varlist=newDoubleLinkedList(6,2,4,8,6,8,4,2);varcallback=function(item){//this function return the opposite itemreturn-item;};list.sort(callback);//list contains 8, 7, 6, 4, 3, 2
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB,itemB);varcallback=function(item){//this function return the key of the itemreturnitem.key;};list.sort(callback);//list contains itemB, itemB, itemA
This method reverses the items stored in the list
varlist=newDoubleLinkedList(6,3,2,7,4,8);list.reverse();//list contains 8, 4, 7, 2, 3, 6
This method returns the number of the items that satisfy the condition represented by the callback function.
varlist=newDoubleLinkedList(6,2,4,8,6,8,4,2);varcallback=function(item){//this function checks if there is a number lower than 5.returnitem<5;};list.count(callback);//4
In this example we deal with more complex items.
varitemA={parent:null; key:0};varitemB={parent:itemA; key:1};varlist=newDoubleLinkedList(itemA,itemB,itemB);varcallback=function(item){//this function checks if there is an item whose parent is itemAreturnitem.parent===itemA;};list.count(callback);//2
This method append the list at the end of this list.
varlistA=newDoubleLinkedList(6,8,4,2);varlistB=newDoubleLinkedList(7,8,5,3);listA.join(listB);//listA contains 6, 8, 4, 2, 7, 8, 5, 3
This method divides the list at the position index and return a list containing the items cut from the list.
varlistA=newDoubleLinkedList(6,8,4,2);varlistB=listA.divide(2);//listB contains 4, 2 and listA contains 6, 8
This method divides the list into an array of lists each one of a maximum length equals to the parameter size.
varlist=newDoubleLinkedList(6,8,4,2,5,7,9,1);varlists=list.split(3);//lists contains 3 listslists[0];//contains 6, 8, 4lists[1];//contains 2, 5, 7lists[2];//contains 9, 1
This method returns a clone of the list. The items are cloned only if there's a methodclone() to invoke, otherwise they will be shared with the old list. This problem there is not if items are not object.
varlist=newDoubleLinkedList(6,8,4,2);varclone=list.clone();//clone contains 6, 8, 4, 2
This method returns a clone of the list containing only one copy of the same item. The items are cloned only if there's a methodcloneDistinct() to invoke or at least a methodclone(), otherwise they will be shared with the old list. This problem there is not if items are not object.
varlist=newDoubleLinkedList(2,8,4,6,8,4,2,6);varclone=list.cloneDistinct();//clone contains 2, 8, 4, 6
m: 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 beO(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 beO(n2).