C - write a code for implementation of doubly linked list with use of single pointer in each node

GeekInterview.com > Interview Questions > Programming > C

Go To First | Previous Question | Next Question

C | Question 186 of 453

write a code for implementation of doubly linked list with use of single pointer in each node

Total Answers and Comments: 7

Last Update: May 09, 2006 Asked by: arati_nayak2000

Sponsored Links

Best Rated Answer

—

No best answer available. Please pick the good answer available or submit your answer.

January 01, 2006 11:05:42

javabond

Member Since: December 2005 Contribution: 1

RE: write a code for implementation of doubly linked l...

struct node{ int X-or; struct node *next;}node;Have a integer in the node which stores the PrevNode ^ NextNode. So at any node you can easily get the address of the previous node by performing an X-or operation with the next node address.

Is this answer useful? Yes | No

January 01, 2006 11:10:56

j_jagdeesh

Member Since: November 2005 Contribution: 1

RE: write a code for implementation of doubly linked l...

Store an extra integer which stores the X-or value of addresses of previous node and the next node. Since you have the option of storing one pointer you can easily retrieve the address of the other node {either previous or next} by performing X-or between the stored integer and the node address (stored one).

Is this answer useful? Yes | No

January 24, 2006 12:56:24

adhyas

RE: write a code for implementation of doubly linked l...

but this solution is as good as having another integer which stores the pointer value directly (instead of having an XORed value). You can always put pointer values and do pointer operations using integer variables.

Is this answer useful? Yes | No

March 16, 2006 22:50:35

chetan_lovely

Member Since: September 2005 Contribution: 2

RE: write a code for implementation of doubly linked l...

#include

struct NODE {
NODE *pNext;
NODE *pPrev;
int nData;
};

NODE *pHead *pTail;

// Appends a node to the end of the list
void AppendNode(NODE *pNode)
{
if (pHead NULL) {
pHead pNode;
pNode->pPrev NULL;
}
else {
pTail->pNext pNode;
pNode->pPrev pTail;
}
pTail pNode;
pNode->pNext NULL;
}

// Inserts a node into the list after pAfter
void InsertNode(NODE *pNode NODE *pAfter)
{
pNode->pNext pAfter->pNext;
pNode->pPrev pAfter;
if (pAfter->pNext ! NULL)
pAfter->pNext->pPrev pNode;
else
pTail pNode;
pAfter->pNext pNode;
}

// Removes the specified node from the list
void RemoveNode(NODE *pNode)
{
if (pNode->pPrev NULL)
pHead pNode->pNext;
else
pNode->pPrev->pNext pNode->pNext;
if (pNode->pNext NULL)
pTail pNode->pPrev;
else
pNode->pNext->pPrev pNode->pPrev;
}

// Deletes the entire list
void DeleteAllNodes()
{
while (pHead ! NULL)
RemoveNode(pHead);
}

void main()
{
NODE *pNode;

// Add items to linked list
for (int i 0; i < 100; i++) {
pNode new NODE;
pNode->nData i;
AppendNode(pNode);
}
// Now display each item in list
for (pNode pHead; pNode ! NULL; pNode pNode->pNext) {
printf( d\n pNode->nData);
}
//
DeleteAllNodes();
}

Is this answer useful? Yes | No

March 28, 2006 04:38:41

viralpatolia

Member Since: March 2006 Contribution: 1

RE: write a code for implementation of doubly linked l...

simple thing....

just keep one pointer variable that will carry address for previous node and not next one....to find out address of next one just use the formula given below...

e.g

struct NODE

{

int *lleft;

int element;

};

certain cases:

1) in first node left will have the address for last node.To find the address of second node use this formula 'lleft+sizeof(NODE)'.

2) if second node the left pointer variable contains address of first node and address of second node can b find out using same formula given above.

3) to maitain last node is little tough...because left pointer variable will carry address of second from last node...but to find out the address of first variable(as per rule of doubly linked list.last node should have right pointer pointed to first node so that it can traverse in circular way)...the formula can be used is

lleft-(sizeof(NODE)*number of NODE in LIST)

it means u need to keep track of number of node present in doubly linked list

Is this answer useful? Yes | No

April 28, 2006 08:15:06

ashutosh_dasgupta

Member Since: March 2006 Contribution: 5

RE: write a code for implementation of doubly linked l...

hi viral

how does doing simple addtion to the addresses will take u to the next node?

as far as i remember the nodes are not in a sequence in the memory. this is true in case of an array but not in dynamically allocated memory as in linked list!

Is this answer useful? Yes | No

May 09, 2006 14:11:55

Xavier Raj

RE: write a code for implementation of doubly linked l...

Hi I agree with Ashtosh since linked list nodes are stored dynamically in memory wherever it has space so the simple addition wont give track of nodes but a junk value.we can construct this only by combining two pointer nodes for single data value.its complex too...!

Is this answer useful? Yes | No

Go To Top

User Name		Remember Me?
Password

Question Bank