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

Commitc40e4cf

Browse files
authored
Refactored code to improve performance of some methods (TheAlgorithms#1284)
* refactored code to improve perfomance* added 'check tail' test* corrected styling and spelling mistake
1 parentc252df5 commitc40e4cf

File tree

2 files changed

+73
-47
lines changed

2 files changed

+73
-47
lines changed

‎Data-Structures/Linked-List/SinglyLinkedList.js

Lines changed: 59 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
11
/* SinglyLinkedList!!
2-
* A linked list is similar to an array, it holds a list of values.
3-
* However, links in a linked list do not have indexes. With
4-
* a linked list you do not need to predetermine its size as
5-
* it grows and shrinks as it is edited. This is an example of
6-
* a singly linked list.
7-
*/
2+
* A linked list is similar to an array, it holds a list of values.
3+
* However, links in a linked list do not have indexes. With
4+
* a linked list you do not need to predetermine its size as
5+
* it grows and shrinks as it is edited. This is an example of
6+
* a singly linked list.
7+
*/
88

99
// Methods - size, head, addLast, addFirst, addAt, removeFirst, removeLast, remove, removeAt, indexOf, isEmpty, elementAt, findMiddle, get, clean, rotateListRight
1010

@@ -18,6 +18,7 @@ class Node {
1818
classLinkedList{
1919
constructor(listOfValues){
2020
this.headNode=null
21+
this.tailNode=null
2122
this.length=0
2223

2324
if(listOfValuesinstanceofArray){
@@ -42,6 +43,11 @@ class LinkedList {
4243
returnthis.headNode?.data||null
4344
}
4445

46+
// Returns the tail
47+
tail(){
48+
returnthis.tailNode?.data||null
49+
}
50+
4551
// Return if the list is empty
4652
isEmpty(){
4753
returnthis.length===0
@@ -53,23 +59,22 @@ class LinkedList {
5359
if(this.headNode===null){
5460
returnthis.addFirst(element)
5561
}
56-
let{ currentNode}=this.initiateNodeAndIndex()
57-
58-
// Loop till there is a node present in the list
59-
while(currentNode.next){
60-
currentNode=currentNode.next
61-
}
62-
6362
constnode=newNode(element)
6463
// Adding node at the end of the list and increase the length
65-
currentNode.next=node
64+
this.tailNode.next=node
65+
this.tailNode=node
6666
this.length++
6767
returnthis.size()
6868
}
6969

7070
// add a node at first it to linklist
7171
addFirst(element){
7272
constnode=newNode(element)
73+
// Check if its the first element
74+
if(this.headNode===null){
75+
this.tailNode=node
76+
}
77+
// Adding node at the start of the list and increase the length
7378
node.next=this.headNode
7479
this.headNode=node
7580
this.length++
@@ -78,27 +83,36 @@ class LinkedList {
7883

7984
// remove the first from the linklist
8085
removeFirst(){
86+
// Check if head is null
87+
if(this.headNode===null){
88+
returnnull
89+
}
90+
// Removing node at the start of the list and decrease the length
8191
constremovedNode=this.headNode
82-
if(this.length>0){
83-
this.headNode=this.headNode.next
84-
this.length--
92+
this.headNode=this.headNode.next
93+
this.length--
94+
// Check if the list is empty
95+
if(this.isEmpty()){
96+
this.tailNode=null
8597
}
8698
returnremovedNode?.data
8799
}
88100

89101
// remove the last from the linklist
90102
removeLast(){
91103
if(this.isEmpty())returnnull
104+
// Check if there is only one element
92105
if(this.length===1){
93106
returnthis.removeFirst()
94107
}
95-
let{ currentIndex, currentNode}=this.initiateNodeAndIndex()
96-
while(currentIndex!==this.length-2){
97-
currentIndex++
108+
// Removing node at the end of the list and decrease the length
109+
constremovedNode=this.tailNode
110+
let{ currentNode}=this.initiateNodeAndIndex()
111+
while(currentNode.next.next){
98112
currentNode=currentNode.next
99113
}
100-
constremovedNode=currentNode.next
101114
currentNode.next=null
115+
this.tailNode=currentNode
102116
this.length--
103117
returnremovedNode.data
104118
}
@@ -112,13 +126,17 @@ class LinkedList {
112126
if(currentNode.data===element){
113127
returnthis.removeFirst()
114128
}
129+
// Check if the tail node is the element to remove
130+
if(this.tailNode.data===element){
131+
returnthis.removeLast()
132+
}
115133
// Check which node is the node to remove
116-
while(currentNode?.next){
134+
while(currentNode.next){
117135
if(currentNode.next.data===element){
118136
removedNode=currentNode.next
119137
currentNode.next=currentNode.next.next
120138
this.length--
121-
break
139+
returnremovedNode.data
122140
}
123141
currentNode=currentNode.next
124142
}
@@ -127,10 +145,9 @@ class LinkedList {
127145

128146
// Returns the index of the element passed as param otherwise -1
129147
indexOf(element){
130-
let{ currentIndex, currentNode}=this.initiateNodeAndIndex()
131-
148+
if(this.isEmpty())return-1
149+
let{ currentNode, currentIndex}=this.initiateNodeAndIndex()
132150
while(currentNode){
133-
// Checking if the node is the element we are searching for
134151
if(currentNode.data===element){
135152
returncurrentIndex
136153
}
@@ -185,7 +202,7 @@ class LinkedList {
185202
thrownewRangeError('Out of Range index')
186203
}
187204
if(index===0)returnthis.removeFirst()
188-
if(index===this.length)returnthis.removeLast()
205+
if(index===this.length-1)returnthis.removeLast()
189206

190207
let{ currentIndex, currentNode}=this.initiateNodeAndIndex()
191208
while(currentIndex!==index-1){
@@ -194,7 +211,6 @@ class LinkedList {
194211
}
195212
constremovedNode=currentNode.next
196213
currentNode.next=currentNode.next.next
197-
// Decrementing the length
198214
this.length--
199215
returnremovedNode.data
200216
}
@@ -215,6 +231,7 @@ class LinkedList {
215231
// make the linkedList Empty
216232
clean(){
217233
this.headNode=null
234+
this.tailNode=null
218235
this.length=0
219236
}
220237

@@ -226,34 +243,28 @@ class LinkedList {
226243
list.push(currentNode.data)
227244
currentNode=currentNode.next
228245
}
229-
230246
returnlist
231247
}
232248

233249
// Method for Rotating a List to the right by k places
234250
rotateListRight(k){
235-
leti=0
251+
if(!this.headNode)return
236252
letcurrent=this.headNode
237-
while(current){
238-
i++
253+
lettail=this.tailNode
254+
letcount=1
255+
while(current.next){
256+
count++
239257
current=current.next
240258
}
241-
k%=i
242-
current=this.headNode
243-
letprev=null
244-
while(k--){
245-
if(!current||!current.next){
246-
returncurrent
247-
}else{
248-
while(current.next){
249-
prev=current
250-
current=current.next
251-
}
252-
prev.next=current.next
253-
current.next=this.headNode
254-
this.headNode=current
255-
}
259+
current.next=this.headNode
260+
tail=current
261+
k%=count
262+
while(count-k>0){
263+
tail=tail.next
264+
count--
256265
}
266+
this.headNode=tail.next
267+
tail.next=null
257268
}
258269

259270
// Method to iterate over the LinkedList
@@ -286,6 +297,7 @@ class LinkedList {
286297
prev=head
287298
head=next
288299
}
300+
this.tailNode=this.headNode
289301
this.headNode=prev
290302
};
291303
}

‎Data-Structures/Linked-List/test/SinglyLinkedList.test.js

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -150,6 +150,20 @@ describe('SinglyLinkedList', () => {
150150
expect(list.head()).toBe(30)
151151
})
152152

153+
it('Check tail',()=>{
154+
constlist=newLinkedList()
155+
expect(list.tail()).toBe(null)
156+
157+
list.addLast(10)
158+
expect(list.tail()).toBe(10)
159+
160+
list.addLast(20)
161+
expect(list.tail()).toBe(20)
162+
163+
list.addFirst(30)
164+
expect(list.tail()).toBe(20)
165+
})
166+
153167
it('Check size',()=>{
154168
constlist=newLinkedList()
155169
expect(list.size()).toBe(0)

0 commit comments

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