Linked list remove node...I am banging my head!!

csstudent123 (161)
pls help me. how to remove node from linked list. I am trying to implement this in a file record to remove data from struct..I dont know how addressing in linked list work for structs;

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
 
#include <iostream>
#include<fstream>
#include<cstring>
#include<cstdlib>

using namespace std;
struct node{

	int val;
	node* next;

};


void remove(int, node*);
void remove(int val, node* some){

	
	node* curr;
	curr=some;
	
	for(int i=0;i<3;i++){
		curr=curr->next;
		if(i==val){
			delete curr;
		
		}
	
	}
	
	
}

int main(){
	
	node ptc[3];
	node* head=new node;
	int val=2;
	for(int i=0; i<3;i++){
		ptc[i].val=i;
	
	}
	
	remove(val, head);
	
	for(int i=0; i<3;i++){
		cout<<ptc[i].val<<endl;
	
	}
	return 0;
	
	

}


segmentation fault
Last edited on
MiiNiPaa (5455)
node* head=new node; head->next is not initialized and pointing to random memory.

curr=curr->next; And here you are using it, creating segfault.
doug4 (453)
First of all, you are confused as to what a linked list is. There is no array in a linked list, so you can get rid of all references to ptc.

A linked list is a set of nodes. Each node has a value and a pointer to the next node in the list. That is what you defined in lines 6 - 12.

Before you can delete nodes from a linked list, you have to add nodes to the linked list first. When you add a node, you must allocate the node (using new), assign the "next" pointer of the previous node to the address of the new node, and assign the "next" pointer of the new node to what the previous node used to point to.

There is also the special case of inserting a node as the first element of an existing list (including the first element of an empty list).

I would suggest the following starting point:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
/* various includes */
struct node ... /* same as what you have */

void addToBack(node** theList, int value)
{
    .... /* This is what you have to implement */
}

int main()
{
    node* head = NULL;  /* Start with an empty list */
    for (int i = 0; i < 3; ++i)
    {
        addToBack(&head, i);
    }
}


Figure out how to add nodes to the list, and then print them out to make sure you have them inserted properly. After that you can start thinking about removing the nodes.
csstudent123 (161)
Am I correct in assigning the first node as this address?

node* curr;
curr=some;//same as head=new node.
doug4 (453)
In what context?
chrisname (7305)
To remove a node from the tail (i.e. any element after the first) of a singly-linked list:
1. let prev be the element before the one being removed
2. let tmp = prev->next
3. prev->next = tmp->next (for the last element, tmp->next will be NULL, but we aren't going to dereference it)
4. delete tmp

Here's a visualisation of deleting the 3rd element in a four-element linked-list:
1. +-------+------+------+------+------+
   | Elem: | Head | 2nd  | 3rd  | 4th  |
   +-------+------+------+------+------+
   | Ptr:  | 2nd  | 3rd  | 4th  | null |
   +-------+------+------+------+------+
2. +-------+------+------+------+------+
   | Elem: | Head | 2nd  | 3rd  | 4th  |
   +-------+------+------+------+------+
   | Ptr:  | 2nd  | 4th  | 4th  | null |
   +-------+------+------+------+------+
3. +-------+------+------+------+
   | Elem: | Head | 2nd  | 4th  |
   +-------+------+------+------+
   | Ptr:  | 2nd  | 4th  | null |
   +-------+------+------+------+


To remove the head (i.e. first) element:
1. let next = head->next
2. delete head
3. head = next
Last edited on
csstudent123 (161)
Is my destructor for linked list ok the way I wrote it ?

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
 
linkedlist::~linkedlist(){

    if(head==NULL){

       //do nothing
    }

    else{
        nodeptr tmp, cur;

        cur->next=head;
        tmp->next=head;

        while(cur->next){
            cur=cur->next;
            delete tmp;
            tmp=cur->next;
        }
        delete tmp;
        delete head;
        tmp=NULL;
        cur=NULL;
        head=NULL;
    }


}
Last edited on
dhayden (599)
No. You don't initialize cur or tmp, so lines 11 and 12 set random bits of memory to head. Even if that didn't cause a problem I think you're deleting the head twice and you aren't deleting the second item.

You've made it much too complicated. You can simply do
1
2
3
4
5
 
while (head) {
    nodeptr tmp=head->next;
    delete head;
    head = tmp;
}

csstudent123 (161)
whats the difference between

var1->next=var2 and var1=var2->next and var1=var2
Last edited on
dhayden (599)
Refer back to the definition of a node:
1
2
3
4
 
struct node{
	int val;
	node* next;
};


This will be too hard to explain without a diagram, but it's critical that you understand the difference. See here: http://en.wikipedia.org/wiki/Linked_list#Linearly_linked_lists


dhayden (599)
It sounds like you don't really get how linked lists work. See this article for some goo material:
http://en.wikipedia.org/wiki/Linked_list#Linearly_linked_lists
csstudent123 (161)
thanks..data structure is new to me
Registered users can post here. Sign in or register to post.

C++

Forum