Skip to content

Commit 098286d

Browse files
author
Caley Woods
committed
Add linked list data structure
1 parent 5614404 commit 098286d

4 files changed

Lines changed: 177 additions & 1 deletion

File tree

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,3 @@
1-
+ linked list
21
+ double linked list
32
+ is palindrome
43
+ sqap nodes
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
const node = require('./Node');
2+
let Node = node.Node;
3+
4+
class LinkedList {
5+
constructor() {
6+
this.head = null;
7+
}
8+
9+
append(data) {
10+
if (this.head === null) {
11+
this.head = new Node(data);
12+
return;
13+
}
14+
15+
let currentNode = this.head;
16+
17+
while (currentNode.next !== null) {
18+
currentNode = currentNode.next;
19+
}
20+
21+
currentNode.next = new Node(data);
22+
}
23+
24+
prepend(data) {
25+
const newHead = new Node(data);
26+
newHead.next = this.head;
27+
this.head = newHead;
28+
}
29+
30+
deleteWithValue(key, value) {
31+
if (this.head === null) return false;
32+
33+
if (this.head.data[key] === value) {
34+
this.head = this.head.next;
35+
return true;
36+
}
37+
38+
let currentNode = this.head;
39+
40+
while (currentNode.next !== null) {
41+
if (currentNode.next.data[key] === value) {
42+
currentNode.next = currentNode.next.next;
43+
return true;
44+
}
45+
currentNode = currentNode.next;
46+
}
47+
48+
return false;
49+
}
50+
51+
getNodeWithValue(key, value) {
52+
if (this.head === null) return null;
53+
54+
let currentNode = this.head;
55+
56+
if (this.head.data[key] === value) {
57+
return this.head;
58+
}
59+
60+
while (currentNode !== null) {
61+
if (currentNode.data[key] === value) {
62+
return currentNode;
63+
}
64+
65+
currentNode = currentNode.next;
66+
}
67+
68+
return null;
69+
}
70+
}
71+
72+
module.exports = {LinkedList: LinkedList}
Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
const linked = require('./LinkedList');
2+
const node = require('./Node');
3+
let LinkedList = linked.LinkedList;
4+
let Node = node.Node;
5+
6+
test('we can create a new linked list', () => {
7+
const ll = new LinkedList();
8+
expect(ll).toBeDefined();
9+
expect(ll).toHaveProperty('head');
10+
});
11+
12+
test('we can create a new node', () => {
13+
const ll = new LinkedList();
14+
const data = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
15+
const node = new Node(data);
16+
17+
expect(ll).toBeDefined();
18+
expect(node.data).toEqual(data);
19+
});
20+
21+
test('we can append to the linked list', () => {
22+
const ll = new LinkedList();
23+
const data = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
24+
const node = new Node(data);
25+
ll.append(data);
26+
expect(ll.head).toEqual(node);
27+
});
28+
29+
test('we can prepend to the linked list', () => {
30+
const ll = new LinkedList();
31+
const firstData = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
32+
const secondData = {'repoName': 'jest', 'owner': 'facebook'};
33+
const firstNode = new Node(firstData);
34+
const secondNode = new Node(secondData);
35+
36+
ll.append(firstData);
37+
ll.prepend(secondData);
38+
secondNode.next = firstNode;
39+
40+
expect(ll.head).toEqual(secondNode)
41+
});
42+
43+
test('we can delete from the linked list', () => {
44+
const ll = new LinkedList();
45+
46+
const firstData = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
47+
const firstNode = new Node(firstData);
48+
49+
ll.append(firstData);
50+
expect(ll.head).toEqual(firstNode);
51+
52+
ll.deleteWithValue('repoName', 'JavaScriptAlgorithms');
53+
54+
expect(ll.head).toEqual(null);
55+
});
56+
57+
test('we receive false when trying to delete from an empty linked list', () => {
58+
const ll = new LinkedList();
59+
expect (ll.deleteWithValue('repoName', 'nothing')).toBe(false);
60+
});
61+
62+
test('we receive true when trying to delete from an empty linked list', () => {
63+
const ll = new LinkedList();
64+
const firstData = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
65+
66+
ll.append(firstData);
67+
68+
expect (ll.deleteWithValue('repoName', 'JavaScriptAlgorithms')).toBe(true);
69+
});
70+
71+
test('we can retrieve a node from the linked list', () => {
72+
const ll = new LinkedList();
73+
74+
const firstData = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
75+
const secondData = {'repoName': 'jest', 'owner': 'facebook'};
76+
const secondNode = new Node(secondData);
77+
78+
ll.append(firstData);
79+
ll.append(secondData);
80+
81+
const fb = ll.getNodeWithValue('owner', 'facebook');
82+
83+
expect(fb).toEqual(secondNode);
84+
});
85+
86+
test('we receive null when retreiving a non-existant node', () => {
87+
const ll = new LinkedList();
88+
89+
const firstData = {'repoName': 'JavaScriptAlgorithms', 'owner': 'vJechsmayr'};
90+
const firstNode = new Node(firstData);
91+
92+
ll.append(firstData);
93+
94+
const search = ll.getNodeWithValue('repoName', 'nothing');
95+
96+
expect(search).toBe(null);
97+
});

‎DataStructures/Linked List/Node.js‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
class Node {
2+
constructor (data) {
3+
this.data = data;
4+
this.next = null;
5+
}
6+
}
7+
8+
module.exports = {Node: Node}

0 commit comments

Comments
 (0)