-
Linked List problem
I need some help in writting a linked list program. The program I have to write has six nodes a-f. and I have delete the third node in the list and then show the list again missing the third node. I know how delete tails and headers but can't figure this out. Please help.
-
Well first is it a doubly-linked list or singly-linked list?
Then when in doubt draw a picture. What I mean by this is, draw a box, this represents a node. So you need six boxes.
Then draw arrows to connect the boxes, these are your pointers.
This is a start. Go From there.
kwigibo
-
if its a single linked list, then you really need a temp pointer, so that once your one link away from the one you delete you would do:
tempptr = node->next;
node->next=node->next->next;
free(tempptr);
this way you link the list around the one you got rid of then free up the memory. But i think kwigibo's answer of drawing boxes will help the most, making sure that each box will disappear unless something is holding onto it (ie a pointer), see if you were to use the above without the tempptr then you would have waisted memory until the program exits.
Hope this helps
-
Let's say you have a list looking like this:
NODE_A --> NODE_B --> NODE_C ...
and you want to delete NODE_B.
The crucial point here is not to forget to link nodes A and C BEFORE you erase node B.
-
This is pretty easy to do:
Code:
typedef struct NodeStruct
{
int iData;
struct NodeStruct* pNext;
} NodeType;
NodeType* DeleteNode( NodeType* pCurrNode, int iValue )
{
NodeType* pTemp;
if( pCurrNode == NULL ) return NULL;
else if( --iValue < 0 ) return pCurrNode;
else if( iValue == 0 )
{
pTemp = pCurrNode->pNext;
free( pCurrNode );
return pTemp;
}
else
{
pCurrNode->pNext = DeleteNode( pCurrNode->pNext, iValue );
return pCurrNode;
}
}
If you have your list ready to go with a pointer to the head of the list pHead then you just do this to delete the #3 node:
Code:
pHead = DeleteNode( pHead, 3 );
Replace the 3 with whatever number to delete that particular node. Any value passed into the DeleteNode function less than 1 will have no effect on the list. Values greater than the number of nodes in the list will similarly have no effect on the list.
-
another way without using a recursive function is:
Code:
typedef struct NodeStruct
{
int iData;
struct NodeStruct* next;
} NodeType;
int DeleteNode(NodeType **mainlist, int value)
{
int counter=0;
NodeType *tempptr, *tempptr2;
if(*mainlist == NULL)
return 2; // LIST IS EMPTY
else
{
tempptr = *mainlist;
while((counter<(value-1)) && (tempptr->next!=NULL))
{
tempptr=tempptr->next;
counter++;
}
if(tempptr->next==NULL)
return 1; // NUMBER DOESNT EXIST
else
{
tempptr2 = tempptr->next;
tempptr->next = tempptr->next->next;
free(tempptr2);
}
}
}
but either one will work (think mine works, havent tested it).