8 Replies - 27531 Views - Last Post: 30 January 2013 - 10:05 PM Rate Topic: -----

#1 mrm   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 30-January 13

Dummy nodes in a linked list.

Posted 30 January 2013 - 08:35 PM

Am I doing this right? I need to create a dummy node and assign a "front" and a "back" pointer to it.

struct Node{

 string data;




Is This A Good Question/Topic? 0
  • +

Replies To: Dummy nodes in a linked list.

#2 mrm   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 30-January 13

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 08:44 PM

Sorry here's the rest of it.

struct Node {
	string item;
	Node* next;

	Node(const string& data, Node* const next){
             this.data=data;
             this.next=next;}
};

int main (){

	Node* front;
	Node* back;

//is this how you create a dummy node at the front and assigned the two pointers to it?
	back = front = NULL;

//add to the linked list from back
	tail->next = makeNode("name", NULL);
	tail = tail->next;
}

Node* makeNode(const string& data, Node* const next){
	Node* nptr = new Node(item, next);

	return nptr;
} 


Was This Post Helpful? 0
  • +
  • -

#3 jjl   User is offline

  • Engineer
  • member icon

Reputation: 1271
  • View blog
  • Posts: 4,998
  • Joined: 09-June 09

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 08:46 PM

Quote

Am I doing this right? I need to create a dummy node and assign a "front" and a "back" pointer to it.

Doing what? No that small snippit of code is incorrect. The whole point of a dummy node in a circular list is to keep a circular structure, even if the list is empty. To create a circular list when there are no nodes in the list, the front and back must point the the dummy node itself, not NULL. Here is an example of how to create a dummy node for a doubly linked circular list

struct Node {
   string data;
   Node *front;
   Node *back;
};

int main() {
   Node *dummy = new Node;

   //point front and back to itself
   dummy->front = dummy;
   dummy->back = dummy;

   delete dummy;
   return 0;
}


This post has been edited by jjl: 30 January 2013 - 08:48 PM

Was This Post Helpful? 0
  • +
  • -

#4 mrm   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 30-January 13

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 09:00 PM

Well this is a singly linked list. And the dummy nodes are for easier navigation.
I tried the
 Node* dummy = new Node;
but there is no constructor.
So perhaps
front = makeNode(" ", NULL);
back = front;


?
Was This Post Helpful? 0
  • +
  • -

#5 jjl   User is offline

  • Engineer
  • member icon

Reputation: 1271
  • View blog
  • Posts: 4,998
  • Joined: 09-June 09

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 09:26 PM

Quote

Well this is a singly linked list. And the dummy nodes are for easier navigation.

Create a dummy node for a singly linked list is unusual, but I guess it's done to ease implementation (I disagree).

To create a dummy head node, just create a new node and point it's next pointer to the "real" head of the list.

This post has been edited by jjl: 30 January 2013 - 09:29 PM

Was This Post Helpful? 0
  • +
  • -

#6 mrm   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 30-January 13

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 09:36 PM

So like this
Node* front;

front->next = makeNode("name", NULL);
back = front->next;

?
Was This Post Helpful? 0
  • +
  • -

#7 jjl   User is offline

  • Engineer
  • member icon

Reputation: 1271
  • View blog
  • Posts: 4,998
  • Joined: 09-June 09

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 09:53 PM

Quote

So like this

No, you cannot dereference a pointer that does not point to valid memory. The pointer "front" is allocated on the stack, but you have pointed it to any valid memory. Since you want your front node to be a dummy node, assign the result of makeNode to front rather than front->next.

Node *front = makeNode("dummy", NULL);


This post has been edited by jjl: 30 January 2013 - 09:54 PM

Was This Post Helpful? 0
  • +
  • -

#8 mrm   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 30-January 13

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 09:59 PM

Ok and to add a node to the front then it's...
front->next = makeNode("name", NULL);

?

Ok and to add a node to the front then it's...
front->next = makeNode("name", NULL);

?
Was This Post Helpful? 0
  • +
  • -

#9 jjl   User is offline

  • Engineer
  • member icon

Reputation: 1271
  • View blog
  • Posts: 4,998
  • Joined: 09-June 09

Re: Dummy nodes in a linked list.

Posted 30 January 2013 - 10:05 PM

Quote

Ok and to add a node to the front then it's...

Yes
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1