8000 update (#1) · TheAlgorithms/JavaScript@95bba0b · GitHub
[go: up one dir, main page]
Skip to content

Commit 95bba0b

Browse files
itsvinayakNourBennourStepfenShawngithub-actionshmizz
authored
update (#1)
* Graph Theory * Delete Graphs * Graph * Dijkstra Smallest Path * DijkstraSmallestPath after fixing some errors. * Topological Sort directed graphs * correcting name of file * updating DIRECTORY.md * doublylinkedlist * add-doublylinkedlist * add-doublylinkedlist * change in Directory.md * updating DIRECTORY.md Co-authored-by: Nur69 <60115902+Nur69@users.noreply.github.com> Co-authored-by: Stepfen Shawn <m18824909883@163.com> Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: hmizz <hamza.chabchoub@medtech.tn>
1 parent 31cb7fe commit 95bba0b

File tree

5 files changed

+472
-0
lines changed

5 files changed

+472
-0
lines changed

‎DIRECTORY.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
* Heap
2323
* [MinPriorityQueue](https://github.com/TheAlgorithms/Javascript/blob/master/Data%20Structures/Heap/MinPriorityQueue.js)
2424
* Linked List
25+
* [DoublyLinkedList](https://github.com/TheAlgorithms/Javascript/blob/master/Data%20Structures/Linked%20List/DoublyLinkedList.js)
2526
* [singlylinklist](https://github.com/TheAlgorithms/Javascript/blob/master/Data%20Structures/Linked%20List/singlylinklist.js)
2627
* Queue
2728
* [Queue](https://github.com/TheAlgorithms/Javascript/blob/master/Data%20Structures/Queue/Queue.js)
@@ -43,8 +44,10 @@
4344
## maths
4445
* [abs](https://github.com/TheAlgorithms/Javascript/blob/master/maths/abs.js)
4546
* [average mean](https://github.com/TheAlgorithms/Javascript/blob/master/maths/average_mean.js)
47+
* [DijkstraSmallestPath](https://github.com/TheAlgorithms/Javascript/blob/master/maths/DijkstraSmallestPath.js)
4648
* [factorial](https://github.com/TheAlgorithms/Javascript/blob/master/maths/factorial.js)
4749
* [find lcm](https://github.com/TheAlgorithms/Javascript/blob/master/maths/find_lcm.js)
50+
* [graph](https://github.com/TheAlgorithms/Javascript/blob/master/maths/graph.js)
4851

4952
## Search
5053
* [binarySearch](https://github.com/TheAlgorithms/Javascript/blob/master/Search/binarySearch.js)
@@ -68,4 +71,5 @@
6871
* [radixSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/radixSort.js)
6972
* [selectionSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/selectionSort.js)
7073
* [shellSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/shellSort.js)
74+
* [TopologicalSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/TopologicalSort.js)
7175
* [wiggleSort](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/wiggleSort.js)

‎Data Structures/Linked List/DoublyLinkedList.js

Lines changed: 197 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,197 @@
1+
//Hamza chabchoub contribution for a university project
2+
function doubleLinkedList() {
3+
let Node = function(element) {
4+
this.element = element;
5+
this.next = null;
6+
this.prev = null;
7+
}
8+
9+
let length = 0;
10+
let head = null;
11+
let tail = null;
12+
13+
//Add new element
14+
this.append = function(element) {
15+
let node = new Node(element);
16+
17+
if(!head){
18+
head = node;
19+
tail = node;
20+
}else{
21+
node.prev = tail;
22+
tail.next = node;
23+
tail = node;
24+
}
25+
26+
length++;
27+
}
28+
29+
30+
//Add element
31+
this.insert = function(position, element) {
32+
33+
//Check of out-of-bound values
34+
if(position >= 0 && position <= length){
35+
let node = new Node(element),
36+
current = head,
37+
previous,
38+
index = 0;
39+
40+
if(position === 0){
41+
if(!head){
42+
head = node;
43+
tail = node;
44+
}else{
45+
node.next = current;
46+
current.prev = node;
47+
head = node;
48+
}
49+
}else if(position === length){
50+
current = tail;
51+
current.next = node;
52+
node.prev = current;
53+
tail = node;
54+
}else{
55+
while(index++ < position){
56+
previous = current;
57+
current = current.next;
58+
}
59+
60+
node.next = current;
61+
previous.next = node;
62+
63+
//New
64+
current.prev = node;
65+
node.prev = previous;
66+
}
67+
68+
length++;
69+
return true;
70+
}else{
71+
return false;
72+
}
73+
}
74+
75+
//Remove element at any position
76+
this.removeAt = function(position){
77+
//look for out-of-bounds value
78+
if(position > -1 && position < length){
79+
let current = head, previous, index = 0;
80+
81+
//Removing first item
82+
if(position === 0){
83+
head = current.next;
84+
85+
//if there is only one item, update tail //NEW
86+
if(length === 1){
87+
tail = null;
88+
}else{
89+
head.prev = null;
90+
}
91+
}else if(position === length - 1){
92+
current = tail;
93+
tail = current.prev;
94+
tail.next = null;
95+
}else{
96+
while(index++ < position){
97+
previous = current;
98+
current = current.next;
99+
}
100+
101+
//link previous with current's next - skip it
102+
previous.next = current.next;
103+
current.next.prev = previous;
104+
}
105+
106+
length--;
107+
return current.element;
108+
}else{
109+
return null;
110+
}
111+
}
112+
113+
//Get the indexOf item
114+
this.indexOf = function(elm){
115+
let current = head,
116+
index = -1;
117+
118+
//If element found then return its position
119+
while(current){
120+
if(elm === current.element){
121+
return ++index;
122+
}
123+
124+
index++;
125+
current = current.next;
126+
}
127+
128+
//Else return -1
129+
return -1;
130+
};
131+
132+
//Find the item in the list
133+
this.isPresent = (elm) => {
134+
return this.indexOf(elm) !== -1;
135+
};
136+
137+
//Delete an item from the list
138+
this.delete = (elm) => {
139+
return this.removeAt(this.indexOf(elm));
140+
};
141+
142+
//Delete first item from the list
143+
this.deleteHead = function(){
144+
this.removeAt(0);
145+
}
146+
147+
//Delete last item from the list
148+
this.deleteTail = function(){
149+
this.removeAt(length-1);
150+
}
151+
152+
//Print item of the string
153+
this.toString = function(){
154+
let current = head,
155+
string = '';
156+
157+
while(current){
158+
string += current.element + (current.next ? '\n' : '');
159+
current = current.next;
160+
}
161+
162+
return string;
163+
};
164+
165+
//Convert list to array
166+
this.toArray = function(){
167+
let arr = [],
168+
current = head;
169+
170+
while(current){
171+
arr.push(current.element);
172+
current = current.next;
173+
}
174+
175+
return arr;
176+
};
177+
178+
//Check if list is empty
179+
this.isEmpty = function(){
180+
return length === 0;
181+
};
182+
183+
//Get the size of the list
184+
this.size = function(){
185+
return length;
186+
}
187+
188+
//Get the head
189+
this.getHead = function() {
190+
return head;
191+
}
192+
193+
//Get the tail
194+
this.getTail = function() {
195+
return tail;
196+
}
197+
}

‎Sorts/TopologicalSort.js

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
function TopologicalSorter() {
2+
var graph = {},
3+
isVisitedNode,
4+
finishTimeCount,
5+
finishingTimeList,
6+
nextNode;
7+
8+
this.addOrder = function (nodeA, nodeB) {
9+
nodeA = String(nodeA);
10+
nodeB = String(nodeB);
11+
graph[nodeA] = graph[nodeA] || [];
12+
graph[nodeA].push(nodeB);
13+
}
14+
15+
this.sortAndGetOrderedItems = function () {
16+
isVisitedNode = Object.create(null);
17+
finishTimeCount = 0;
18+
finishingTimeList = [];
19+
20+
for (var node in graph) {
21+
if (graph.hasOwnProperty(node) && !isVisitedNode[node]) {
22+
dfsTraverse(node);
23+
}
24+
}
25+
26+
finishingTimeList.sort(function (item1, item2) {
27+
return item1.finishTime > item2.finishTime ? -1 : 1;
28+
});
29+
30+
return finishingTimeList.map(function (value) { return value.node })
31+
}
32+
33+
function dfsTraverse(node) {
34+
isVisitedNode[node] = true;
35+
if (graph[node]) {
36+
for (var i = 0; i < graph[node].length; i++) {
37+
nextNode = graph[node][i];
38+
if (isVisitedNode[nextNode]) continue;
39+
dfsTraverse(nextNode);
40+
}
41+
}
42+
43+
finishingTimeList.push({
44+
node: node,
45+
finishTime: ++finishTimeCount
46+
});
47+
}
48+
}
49+
50+
51+
/* TEST */
52+
var topoSorter = new TopologicalSorter();
53+
topoSorter.addOrder(5, 2);
54+
topoSorter.addOrder(5, 0);
55+
topoSorter.addOrder(4, 0);
56+
topoSorter.addOrder(4, 1);
57+
topoSorter.addOrder(2, 3);
58+
topoSorter.addOrder(3, 1);
59+
console.log(topoSorter.sortAndGetOrderedItems());

0 commit comments

Comments
 (0)
0