-
Notifications
You must be signed in to change notification settings - Fork 98
Linked List
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.
Wikipedia
var listA = new LinkedList(); //an empty list
var listB = new LinkedList(0, 1, 2, 3); //listB contains 0, 1, 2, 3
var listC = new LinkedList(Range(0, 3)); //listC contains 0, 1, 2, 3This 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 LinkedList();
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 LinkedList();
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 LinkedList();
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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(6, 8, 4, 2, 7);
list.modifyAt(1, 6); //list contains 6, 6, 4, 2, 7This method empty the list.
var list = new LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(6, 8, 4, 2);
list.toArray(); //[6, 8, 4, 2]This method fill the list from the array.
var list = new LinkedList();
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 LinkedList();
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 LinkedList();
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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 returns the number of the items that satisfy the condition represented by the callback function.
var list = new LinkedList(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 LinkedList(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 LinkedList(6, 8, 4, 2);
var listB = new LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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 LinkedList(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).