[Solved]How to fix this memory leakage issue?

[PeterHu]

Randomly picked up a singlar linkedlist example from the internet,found there is a memory leakage from line 95 in

Code: Pascal  [Select][+][-]

1. procedure insertAt(head:PNode;pos,value:integer);

But I was stuck in coming up with a solution since it does not help on  just calling dispose(newNode) at the end of the insertAt procedure.

Help would be appreciated.

Code: Pascal  [Select][+][-]

1.  
2. program project1;
3.  
4. const SIZE=10;
5.  
6. type
7.   PNode=^Node;
8.   Node=record
9.     data:integer;
10.     next:PNode;
11.   end;
12.  
13. procedure printAll(head:PNode);
14. var
15.   tmp:PNode;
16. begin
17.   tmp:=head;
18.   write('Linkedlist contains:');
19.   while(tmp^.next<>nil) do
20.     begin
21.       write(tmp^.data,' ,');
22.       tmp:=tmp^.next;
23.     end;
24.     write(tmp^.data);
25.     writeln;
26. end;
27. function length(head:PNode):integer;
28. var
29.   tmp:PNode;
30.   count:integer;
31. begin
32.   tmp:=head;
33.   count:=0;
34.   while(tmp<>nil) do
35.     begin
36.       tmp:=tmp^.next;
37.       count+=1;
38.     end;
39.   length:=count;
40. end;
41. function init(head:PNode;value:integer):PNode;
42. begin
43.   head^.data:=value;
44.   head^.next:=nil;
45.   init:=head;
46. end;
47. function addToStart(head:PNode;value:integer):PNode;
48. var
49.   tmp:PNode;
50. begin
51.   new(tmp);
52.   tmp^.data:=value;
53.   tmp^.next:=head;
54.   addToStart:=tmp;
55.  
56. end;
57. procedure addToTail(head:PNode;value:integer);
58. var
59.   tmp,newNode:PNode;
60. begin
61.   tmp:=head;
62.   while(tmp^.next<>nil) do
63.     begin
64.       tmp:=tmp^.next;
65.     end;
66.   new(newNode);
67.   newNode^.data:=value;
68.   newNode^.next:=nil;
69.   tmp^.next:=newNode;
70. end;
71.  
72. procedure addAt(head:PNode;pos,value:integer);
73. var
74.   tmp,tmp2,newNode:PNode;
75.   count:integer;
76. begin
77.   if(pos>length(head)) then
78.   begin
79.     writeln('AddAt: ',pos,' out of range');
80.   end
81.   else if(pos=1) or (pos=length(head)) then
82.   begin
83.     writeln('Use addToStart to head or addToTail');
84.   end
85.   else
86.   begin
87.     tmp:=head;
88.     count:=1;
89.     while(count<pos) do
90.       begin
91.         tmp2:=tmp;
92.         tmp:=tmp^.next;
93.         count+=1;
94.       end;
95.     new(newNode);
96.     newNode^.data:=value;
97.     newNode^.next:=tmp;
98.     tmp2^.next:=newNode;
99.   end;
100.  
101. end;
102. function removeStart(head:PNode):PNode;
103. begin
104.   removeStart:=head^.next;
105. end;
106.  
107. procedure removeEnd(head:PNode);
108. var
109.   tmp,newNode:PNode;
110. begin
111.   tmp:=head;
112.   while(tmp^.next<>nil) do
113.     begin
114.       newNode:=tmp;
115.       tmp:=tmp^.next;
116.     end;
117.   newNode^.next:=nil;
118. end;
119. procedure removeX(X:integer;head:PNode);
120. var
121.   tmp,newNode:PNode;
122. begin
123.   tmp:=head;
124.   while(tmp^.data<>X) do
125.     begin
126.       newNode:=tmp;
127.       tmp:=tmp^.next;
128.     end;
129.     newNode^.next:=tmp^.next;
130. end;
131.  
132. var
133.   head:PNode;
134.   index:integer;
135. begin
136.   new(head);
137.   head:=init(head,1);
138.   write('Init(head,1): ');
139.   printAll(head);
140.  
141.   writeln;
142.   for index:=2 to SIZE do
143.     addToTail(head,index);
144.  
145.   write('AddToEnd(head,2-10): ');
146.   printAll(head);
147.  
148.   writeln;
149.   head:=addToStart(head,0);
150.   write('AddToStart(head,0): ');
151.   printAll(head);
152.  
153.   writeln;
154.   addAt(head,5,100);
155.   write('addAt(head,5,100): ');
156.   printAll(head);
157.  
158.   writeln;
159.   head:=removeStart(head);
160.   write('removeStart(head): ');
161.   printAll(head);
162.  
163.   writeln;
164.   removeEnd(head);
165.   write('removeEnd(head): ');
166.   printAll(head);
167.  
168.   writeln;
169.   removeX(100,head);
170.   write('removeX(head,100): ');
171.   printAll(head);
172.  
173.   dispose(head);
174.  
175.   writeln;
176.   readln;
177. end.
178.              
179.  

[Thaddy]

Logic error from your side:

Code: Pascal  [Select][+][-]

1. //line 141/42
2.   for index:=2 to SIZE-1 do // <<--------
3.     addToTail(head,index);

Real programmers count from zero, even if instructed to start from 2.....which is the third...
So you have to count to size -1.

Fixed.

BTW using pointer types for such things is often done but never recommended in Pascal.

[cdbc]

Hi
If you want to further peruse linked lists, queues & stacks, written with algorithms by Julian M. Bucknall, you should have a 'LookSee' in the Gitlab repo, THIS thread is pointing to... 
Regards Benny

[PeterHu]

Logic error from your side:

Code: Pascal  [Select][+][-]

1. //line 141/42
2.   for index:=2 to SIZE-1 do // <<--------
3.     addToTail(head,index);

Real programmers count from zero, even if instructed to start from 2.....which is the third...
So you have to count to size -1.

Fixed.

BTW using pointer types for such things is often done but never recommended in Pascal.

I am sorry but it seems this does not fix the memory leakage issue...

[wp]

When you call "RemoveStart" you only set the head pointer to the next element, but you do not dispose the old head here. The same happens with the other "Remove" procedures.

[bytebites]

And  dispose(head) disposes only one node.

[wp]

See highlighted lines to fix the memory leak(s):

Code: Pascal  [Select][+][-]

1. program project1;
2.  
3. const SIZE=10;
4.  
5. type
6.   PNode=^Node;
7.   Node=record
8.     data:integer;
9.     next:PNode;
10.   end;
11.  
12. procedure printAll(head:PNode);
13. var
14.   tmp:PNode;
15. begin
16.   tmp:=head;
17.   write('Linkedlist contains:');
18.   while(tmp^.next<>nil) do
19.     begin
20.       write(tmp^.data,' ,');
21.       tmp:=tmp^.next;
22.     end;
23.     write(tmp^.data);
24.     writeln;
25. end;
26.  
27. function length(head:PNode):integer;
28. var
29.   tmp:PNode;
30.   count:integer;
31. begin
32.   tmp:=head;
33.   count:=0;
34.   while(tmp<>nil) do
35.     begin
36.       tmp:=tmp^.next;
37.       count+=1;
38.     end;
39.   length:=count;
40. end;
41. function init(head:PNode;value:integer):PNode;
42. begin
43.   head^.data:=value;
44.   head^.next:=nil;
45.   init:=head;
46. end;
47.  
48. function addToStart(head:PNode;value:integer):PNode;
49. var
50.   tmp:PNode;
51. begin
52.   new(tmp);
53.   tmp^.data:=value;
54.   tmp^.next:=head;
55.   addToStart:=tmp;
56. end;
57.  
58. procedure addToTail(head:PNode;value:integer);
59. var
60.   tmp,newNode:PNode;
61. begin
62.   tmp:=head;
63.   while(tmp^.next<>nil) do
64.     begin
65.       tmp:=tmp^.next;
66.     end;
67.   new(newNode);
68.   newNode^.data:=value;
69.   newNode^.next:=nil;
70.   tmp^.next:=newNode;
71. end;
72.  
73. procedure addAt(head:PNode;pos,value:integer);
74. var
75.   tmp,tmp2,newNode:PNode;
76.   count:integer;
77. begin
78.   if(pos>length(head)) then
79.   begin
80.     writeln('AddAt: ',pos,' out of range');
81.   end
82.   else if(pos=1) or (pos=length(head)) then
83.   begin
84.     writeln('Use addToStart to head or addToTail');
85.   end
86.   else
87.   begin
88.     tmp:=head;
89.     count:=1;
90.     while(count<pos) do
91.       begin
92.         tmp2:=tmp;
93.         tmp:=tmp^.next;
94.         count+=1;
95.       end;
96.     new(newNode);
97.     newNode^.data:=value;
98.     newNode^.next:=tmp;
99.     tmp2^.next:=newNode;
100.   end;
101. end;
102.  
103. function removeStart(head:PNode):PNode;
104. var
105.   tmp: PNode;
106. begin
107.   tmp := head;
108.   removeStart:=head^.next;
109.   Dispose(tmp);
110. end;
111.  
112. procedure removeEnd(head:PNode);
113. var
114.   tmp,newNode:PNode;
115. begin
116.   tmp:=head;
117.   while(tmp^.next<>nil) do
118.     begin
119.       newNode:=tmp;
120.       tmp:=tmp^.next;
121.     end;
122.   newNode^.next:=nil;
123.   Dispose(tmp);
124. end;
125.  
126. procedure removeX(X:integer;head:PNode);
127. var
128.   tmp,newNode:PNode;
129. begin
130.   tmp:=head;
131.   while(tmp^.data<>X) do
132.     begin
133.       newNode:=tmp;
134.       tmp:=tmp^.next;
135.     end;
136.   newNode^.next:=tmp^.next;
137.   Dispose(tmp);
138. end;
139.  
140. procedure DisposeAll(head: PNode);
141. begin
142.   while head <> nil do
143.     head := RemoveStart(head);
144. end;
145.  
146. var
147.   head:PNode;
148.   index:integer;
149. begin
150.   new(head);
151.   head:=init(head,1);
152.   write('Init(head,1): ');
153.   printAll(head);
154.  
155.   writeln;
156.   for index:=2 to SIZE do
157.     addToTail(head,index);
158.  
159.   write('AddToEnd(head,2-10): ');
160.   printAll(head);
161.  
162.   writeln;
163.   head:=addToStart(head,0);
164.   write('AddToStart(head,0): ');
165.   printAll(head);
166.  
167.   writeln;
168.   addAt(head,5,100);
169.   write('addAt(head,5,100): ');
170.   printAll(head);
171.  
172.   writeln;
173.   head:=removeStart(head);
174.   write('removeStart(head): ');
175.   printAll(head);
176.  
177.   writeln;
178.   removeEnd(head);
179.   write('removeEnd(head): ');
180.   printAll(head);
181.  
182.   writeln;
183.   removeX(100,head);
184.   write('removeX(head,100): ');
185.   printAll(head);
186.  
187.   DisposeAll(head);
188.  
189.   writeln;
190.   readln;
191. end.

[PeterHu]

Thank you.This is extraordinary helpful which has answered almost all my questions under the hood and help me to make a clearer understanding to some fundamental concepts.It is one of the common root cause results in the inability to make good use of a certain language when I tried to solve some certain common problems using whichever programming language I have ever encountered.The above also try to answer why I am stucking with learning  array/pointer/memory stuff.

Still I have one more question left behind:

why it does not have to call dispose(head) right after the recursion call to 'Kill it self'?

Code: Pascal  [Select][+][-]

1.     while head <> nil do
2.        head := RemoveStart(head);
3.  

[cdbc]

Still I have one more question left behind:

why it does not have to call dispose(head) right after the recursion call to 'Kill it self'?

Code: Pascal  [Select][+][-]

1.     while head <> nil do
2.        head := RemoveStart(head);
3.  

Hi
Well, if you look closer in this function:

Code: Pascal  [Select][+][-]

1. function removeStart(head:PNode):PNode;
2. var
3.   tmp: PNode;
4. begin
5.   tmp := head;
6.   removeStart:=head^.next;
7.   Dispose(tmp);
8. end;

It will eventually reach the end of the list, i.e.: the next pointer points to NIL, which is what the above function returns and you check for Head <> nil.
When the loop stops, it's because head has become NIL(head := RemoveStart(head);), thus all the nodes including the Head has been removed / disposed of...
>> Short answer: There's no need << 
HTH
Regards Benny

[jamie]

I don't think the "RemoveStart" needed the Tmp variable, but it does not hurt anything.

Just an observation, maybe I missed something.

Code: Pascal  [Select][+][-]

1.  
2. function removeStart(head:PNode):PNode;
3. begin
4.   removeStart:=head^.next;
5.   Dispose(head);
6. end;
7.  
8.  

Jamie

[PeterHu]

Hi
Well, if you look closer in this function:

Code: Pascal  [Select][+][-]

1. function removeStart(head:PNode):PNode;
2. [code]
3. var
4.   tmp: PNode;
5. begin
6.   tmp := head;
7.   removeStart:=head^.next;
8.   Dispose(tmp);
9. end;

It will eventually reach the end of the list, i.e.: the next pointer points to NIL, which is what the above function returns and you check for Head <> nil.
When the loop stops, it's because head has become NIL(head := RemoveStart(head);), thus all the nodes including the Head has been removed / disposed of...
>> Short answer: There's no need << 
HTH
Regards Benny

Ah yes,yes.Eventually my brain is not running after studying this kind of stuff for a couple of hours.Silly me.

[PeterHu]

I don't think the "RemoveStart" needed the Tmp variable, but it does not hurt anything.

Just an observation, maybe I missed something.

Code: Pascal  [Select][+][-]

1.  
2. function removeStart(head:PNode):PNode;
3. begin
4.   removeStart:=head^.next;
5.   Dispose(head);
6. end;
7.  
8.  

Jamie

You are absolutely right,and may I guess,it is exactly how the machine thinks.
How many hundreds of times when reading about

Code: [Select]

Acquiring memory the pointer points to
Returning back memory the pointer points to
I just felt like I fully understood.However in reality,when encountered the above sample situation,I am not confiditent at the first or even second/third thought and then come up with the conclusion that

header and header^.next are just two different things /they point to different memory address.so below two lines of code is sufficient to work.

Code: [Select]

variable:=head^.next;
dispose(head);

Learnt,thank you!