Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit80ecbe0

Browse files
committed
Move linked list traversals into separate section.
1 parent2feec48 commit80ecbe0

File tree

9 files changed

+147
-60
lines changed

9 files changed

+147
-60
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -109,6 +109,9 @@ a set of rules that precisely define a sequence of operations.
109109
*`B`[Shellsort](src/algorithms/sorting/shell-sort)
110110
*`B`[Counting Sort](src/algorithms/sorting/counting-sort)
111111
*`B`[Radix Sort](src/algorithms/sorting/radix-sort)
112+
***Linked Lists**
113+
*`B`[Straight Traversal](src/algorithms/linked-list/traversal)
114+
*`B`[Reverse Traversal](src/algorithms/linked-list/reverse-traversal)
112115
***Trees**
113116
*`B`[Depth-First Search](src/algorithms/tree/depth-first-search) (DFS)
114117
*`B`[Breadth-First Search](src/algorithms/tree/breadth-first-search) (BFS)
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#Reversed Linked List Traversal
2+
3+
The task is to traverse the given linked list in reversed order.
4+
5+
For example for the following linked list:
6+
7+
![](https://upload.wikimedia.org/wikipedia/commons/6/6d/Singly-linked-list.svg)
8+
9+
The order of traversal should be:
10+
11+
```text
12+
37 → 99 → 12
13+
```
14+
15+
The time complexity is`O(n)` because we visit every node only once.
16+
17+
##Reference
18+
19+
-[Wikipedia](https://en.wikipedia.org/wiki/Linked_list)
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
importLinkedListfrom'../../../../data-structures/linked-list/LinkedList';
2+
importreverseTraversalfrom'../reverseTraversal';
3+
4+
describe('reverseTraversal',()=>{
5+
it('should traverse linked list in reverse order',()=>{
6+
constlinkedList=newLinkedList();
7+
8+
linkedList
9+
.append(1)
10+
.append(2)
11+
.append(3);
12+
13+
consttraversedNodeValues=[];
14+
consttraversalCallback=(nodeValue)=>{
15+
traversedNodeValues.push(nodeValue);
16+
};
17+
18+
reverseTraversal(linkedList,traversalCallback);
19+
20+
expect(traversedNodeValues).toEqual([3,2,1]);
21+
});
22+
});
23+
24+
25+
// it('should reverse traversal the linked list with callback', () => {
26+
// const linkedList = new LinkedList();
27+
//
28+
// linkedList
29+
// .append(1)
30+
// .append(2)
31+
// .append(3);
32+
//
33+
// expect(linkedList.toString()).toBe('1,2,3');
34+
// expect(linkedList.reverseTraversal(linkedList.head, value => value * 2)).toEqual([6, 4, 2]);
35+
// expect(() => linkedList.reverseTraversal(linkedList.head)).toThrow();
36+
// });
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* Traversal callback function.
3+
*@callback traversalCallback
4+
*@param {*} nodeValue
5+
*/
6+
7+
/**
8+
*@param {LinkedListNode} node
9+
*@param {traversalCallback} callback
10+
*/
11+
functionreverseTraversalRecursive(node,callback){
12+
if(node){
13+
reverseTraversalRecursive(node.next,callback);
14+
callback(node.value);
15+
}
16+
}
17+
18+
/**
19+
*@param {LinkedList} linkedList
20+
*@param {traversalCallback} callback
21+
*/
22+
exportdefaultfunctionreverseTraversal(linkedList,callback){
23+
reverseTraversalRecursive(linkedList.head,callback);
24+
}
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#Linked List Traversal
2+
3+
The task is to traverse the given linked list in straight order.
4+
5+
For example for the following linked list:
6+
7+
![](https://upload.wikimedia.org/wikipedia/commons/6/6d/Singly-linked-list.svg)
8+
9+
The order of traversal should be:
10+
11+
```text
12+
12 → 99 → 37
13+
```
14+
15+
The time complexity is`O(n)` because we visit every node only once.
16+
17+
##Reference
18+
19+
-[Wikipedia](https://en.wikipedia.org/wiki/Linked_list)
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
importLinkedListfrom'../../../../data-structures/linked-list/LinkedList';
2+
importtraversalfrom'../traversal';
3+
4+
describe('traversal',()=>{
5+
it('should traverse linked list',()=>{
6+
constlinkedList=newLinkedList();
7+
8+
linkedList
9+
.append(1)
10+
.append(2)
11+
.append(3);
12+
13+
consttraversedNodeValues=[];
14+
consttraversalCallback=(nodeValue)=>{
15+
traversedNodeValues.push(nodeValue);
16+
};
17+
18+
traversal(linkedList,traversalCallback);
19+
20+
expect(traversedNodeValues).toEqual([1,2,3]);
21+
});
22+
});
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
/**
2+
* Traversal callback function.
3+
*@callback traversalCallback
4+
*@param {*} nodeValue
5+
*/
6+
7+
/**
8+
*@param {LinkedList} linkedList
9+
*@param {traversalCallback} callback
10+
*/
11+
exportdefaultfunctiontraversal(linkedList,callback){
12+
letcurrentNode=linkedList.head;
13+
14+
while(currentNode){
15+
callback(currentNode.value);
16+
currentNode=currentNode.next;
17+
}
18+
}

‎src/data-structures/linked-list/LinkedList.js

Lines changed: 0 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -208,40 +208,6 @@ export default class LinkedList {
208208
returnthis.toArray().map(node=>node.toString(callback)).toString();
209209
}
210210

211-
/**
212-
* Traverse through all nodes of the list from head to tail
213-
*@param {*} callback
214-
*@return {LinkedListNode[]}
215-
*/
216-
traverse(callback=undefined){
217-
if(typeofcallback!=='function'){
218-
thrownewTypeError(`traverse method requires a callback function as an argument.\nArgument given:${typeofcallback}`);
219-
}
220-
221-
letcurrentNode=this.head;
222-
consttraversedNodes=[];
223-
224-
while(currentNode){
225-
traversedNodes.push(callback(currentNode.value));
226-
currentNode=currentNode.next;
227-
}
228-
229-
returntraversedNodes;
230-
}
231-
232-
/**
233-
* The items in the list have been traversed in reverse order
234-
*/
235-
reverseTraversal(node,callback=undefined){
236-
if(typeofcallback!=='function'){
237-
thrownewTypeError(`reverseTraverse method requires a callback function as an argument.\nArgument given:${typeofcallback}`);
238-
}
239-
240-
if(!node)return[];
241-
242-
returnthis.reverseTraversal(node.next,callback).concat(callback(node.value));
243-
}
244-
245211
/**
246212
* Reverse a linked list.
247213
*@returns {LinkedList}

‎src/data-structures/linked-list/__test__/LinkedList.test.js

Lines changed: 6 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -218,31 +218,6 @@ describe('LinkedList', () => {
218218
expect(linkedList.find({value:2,customValue:'test5'})).toBeNull();
219219
});
220220

221-
it('should traverse through all nodes of the list from head to tail with callback',()=>{
222-
constlinkedList=newLinkedList();
223-
224-
linkedList
225-
.append(1)
226-
.append(2)
227-
.append(3);
228-
229-
expect(linkedList.traverse(value=>value*2)).toEqual([2,4,6]);
230-
expect(()=>linkedList.traverse()).toThrow();
231-
});
232-
233-
it('should reverse traversal the linked list with callback',()=>{
234-
constlinkedList=newLinkedList();
235-
236-
linkedList
237-
.append(1)
238-
.append(2)
239-
.append(3);
240-
241-
expect(linkedList.toString()).toBe('1,2,3');
242-
expect(linkedList.reverseTraversal(linkedList.head,value=>value*2)).toEqual([6,4,2]);
243-
expect(()=>linkedList.reverseTraversal(linkedList.head)).toThrow();
244-
});
245-
246221
it('should reverse linked list',()=>{
247222
constlinkedList=newLinkedList();
248223

@@ -258,9 +233,14 @@ describe('LinkedList', () => {
258233

259234
// Reverse linked list.
260235
linkedList.reverse();
261-
262236
expect(linkedList.toString()).toBe('3,2,1');
263237
expect(linkedList.head.value).toBe(3);
264238
expect(linkedList.tail.value).toBe(1);
239+
240+
// Reverse linked list back to initial state.
241+
linkedList.reverse();
242+
expect(linkedList.toString()).toBe('1,2,3');
243+
expect(linkedList.head.value).toBe(1);
244+
expect(linkedList.tail.value).toBe(3);
265245
});
266246
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp