Problem with node deletion

I am trying to implement a simple linked-list and then define a function to remove duplicates from the list. Here is my code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<time.h>
#include<set>
using namespace std;
class node
{
public:
	int data;
	node *next;
	
	node(int dat):data(dat)
	{next = 0;}
};

class linked_list
{
	node *first;
	node *last;
	int len;
public:
	linked_list()
	{
		first=last=0;
		len = 0;
	}
	node *get_start()
	{
		return first;
	}
	void set_start(node *beg)
	{
		first = beg;
	}
	void insertAtBeg(int);
	void disp_list(void);
};


void linked_list::insertAtBeg(int val)
{
	node *p = new node(val);
	if(first == 0)
	{
		first = p;len++;
		return;
	}
	p->next = first;
	first = p;
	len++;
}

void linked_list::disp_list()
{
	node *p = first;
	cout<<"\n\n  ";
	while(p!=0)
	{
		cout<<p->data<<" -> ";
		p = p->next;
	}
	cout<<"NULL\n\n";
}

linked_list L;
void remove_dups();

int main()
{
	srand(time(0));
	for(int i=0;i<15;++i)
	{
		L.insertAtBeg((rand()%10));
	}
	L.disp_list();
	remove_dups();
	L.disp_list();
}

void remove_dups()
{
	set<int> chk_dup;
	node * p = L.get_start(), *pre = 0, *del = 0;
	while(p != 0)
	{
		pre = p;
		if(chk_dup.find(p->data) == chk_dup.end())
		{
			chk_dup.insert(p->data);
			p = p->next;
		}
		else
		{
			del = p;
			pre->next = p->next;
			p = p->next;
			cout<<"\n "<<del->data<<" deleted .\n";
			delete del;
		}
	}
}


Here is the output:



  5 -> 3 -> 5 -> 9 -> 8 -> 0 -> 2 -> 5 -> 4 -> 0 -> 9 -> 4 -> 9 -> 6 -> 5 -> NULL


 5 deleted .

 5 deleted .

 0 deleted .

 9 deleted .

 4 deleted .

 9 deleted .

 5 deleted .


  5 -> 3 -> 0 -> 9 -> 8 -> 0 -> 2 -> -474948208 -> 4 -> -474948368 -> -474948432 -> -474948464 -> -474948496 -> 6 ->  -474948560  -> NULL




Why do I still see the deleted nodes with garbage values ,when I have deleted them and also made there previous nodes point to their next node ?

Last edited on
> and also made there previous nodes point to their next node ?
you did not.
`pre = p', `p' is going to be deleted, `pre' points to `p', not to the previous node.
You might also need to update first and last of the list.
Last edited on
Line 84: pre is not pointing to the previous node. It's pointing to the current node.
Line 94: You're setting p->next to itself. You're not modifying the previous instance.

Lines 17-18: You appear to be declaring a doubly linked list, but you're not maintaining the fwd/back pointers correctly.


Thanks everyone for help . It works fine now .

Lines 17-18: You appear to be declaring a doubly linked list, but you're not maintaining the fwd/back pointers correctly.


@AbstractionAnon : Thanks for pointing out , though I was trying to implement a singly linked list only . The last pointer was only to keep track of the end . I have not maintained it as I did not need it till now . Thanks anyways .
Registered users can post here. Sign in or register to post.