Self Contained Linked List

  • (2 Pages)
  • +
  • 1
  • 2

22 Replies - 1756 Views - Last Post: 17 January 2011 - 08:51 PM Rate Topic: -----

#1 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Self Contained Linked List

Posted 06 January 2011 - 08:52 AM

Hey there everyone, I've run into a bit of a problem. I'm currently doing a self contained linked list as an assignment and have run into some issues with some of the functions due to the fact that it's self contained. Here is an example of my class:

class ListNode
{	
public:
	ListNode() : mData(NULL), mFirst(NULL), mLast(NULL), mPrev(NULL), mNext(NULL) {}

	ListNode* Previous()
	{
		if (mPrev != NULL)
			return mPrev;
		else
			return NULL;
	}

	ListNode* Next()
	{
		if (mNext != NULL)
			return mNext;
		else
			return NULL;
	}

	ListNode* Last()
	{
		ListElement *current = mFirst;

		while(current != NULL)
		{
			current = current->mNext;
		}

		return current;
	}

	void Append(ListElement newNode)
	{
		newNode.mPrev = Last();
		*Last()->mNext = newNode;
	}

private:
	ListNode *mData;
	ListNode *mPrev;
	ListNode *mNext;
	ListNode *mFirst;
	ListNode *mLast;
};


I'm supposed to include functions to return the first, last, previous and next nodes, as well as an appending function. My question is, am I on the right path and if not could you set me right?

Thanks so much!

Is This A Good Question/Topic? 0
  • +

Replies To: Self Contained Linked List

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: Self Contained Linked List

Posted 06 January 2011 - 08:57 AM

What is ListElement?

Explain what you're doing here
void Append(ListElement newNode)
{
    newNode.mPrev = Last();
    *Last()->mNext = newNode;
}



It looks like you were getting some compiler error messages and just threw some code down that got rid of them.
Was This Post Helpful? 0
  • +
  • -

#3 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 06 January 2011 - 09:07 AM

In the other constructor I defined, I pass in a C string on which I then get the length and perform memcpy on mData and copy across the elements of the char array. As for the Append function, you're about right. I just wanted to get rid of the compiler errors, I'm not really sure where I'm going with it!
Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,496
  • Joined: 23-August 08

Re: Self Contained Linked List

Posted 06 January 2011 - 09:16 AM

I don't understand where the constructor comes into play in my question, and you failed to answer my first question: what is ListElement?

Also, if this represents a single node in the list, I don't know why you've got First and Last members of this class. A node needs only know the node following it, and the node before it if it's a bi-directional list. The container for the nodes would know the first and last entries in the list. If you're being taught that your nodes need to know the start and end of the list itself, I think you're being taught badly.
Was This Post Helpful? 0
  • +
  • -

#5 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 06 January 2011 - 09:27 AM

I've updated my Last and Append functions.

	ListNode* Last()
	{
		ListElement *current = mFirst;

		while(current->mNext != NULL)
		{
			current = current->mNext;
		}

		return current;
	}

	void Append(ListNode *newNode)
	{
		mLast->mNext = newNode;
		newNode->mNext = NULL;
		newNode->mPrev = mLast;
		mLast = newNode;
	}


However my append function isn't working correctly. I pass in a constructor, and since it's not a pointer, I get a compiler error. My question is this, how can I pass a constructor's address into the function, or do something similar?

As I said before, ListNode is constructing with a C string, which is then copied via memcpy. ListElement was simply a typo error, my apologies.

This post has been edited by Aequitas1: 06 January 2011 - 09:33 AM

Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Re: Self Contained Linked List

Posted 06 January 2011 - 09:40 AM

I think you're confusing List and Node. I'm also not sure what you mean by "self contained."

To me, self contained would mean I never get to the node implementation, which is the way a list should always behave. Why should a user of your list care about nodes?

e.g.
class List {
private:
	struct Node {
		ListElement data;
		Node *prev, *next;
	};
	Node *first, *last, *current;
public:
	List();
	ListElement getCurrent() const;
	bool moveFirst();
	bool moveLast();
	bool movePrevious();
	bool moveNext();
	void append(const ListElement &);
};


Was This Post Helpful? 0
  • +
  • -

#7 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 11 January 2011 - 06:09 AM

I need the node class to be the node and the manager, that's basically what I want to achieve. I need to make this work with a function that was defined prior.
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Re: Self Contained Linked List

Posted 11 January 2011 - 10:46 AM

Facinating. Let's assume you meant to do that.

Are these the only public methods you need?
class ListNode {
public:
	ListNode();
	ListNode* Previous();
	ListNode* Next();
	ListNode* Last();
	void Append(const ListElement &);
};



I'd think you'd at least want a way to get at the value entered. Also, as it stands, a ListNode can have no value at all. Perhaps:
class ListNode {
public:
	ListNode(const ListElement &);
	ListElement &getValue();
};



Or:
class ListNode {
public:
	ListNode();
	ListNode(const ListElement &);
	bool getValue(ListElement &); // returns false if no value available
	bool isEmpty();
};


Was This Post Helpful? 0
  • +
  • -

#9 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Self Contained Linked List

Posted 11 January 2011 - 11:05 AM

Seems like too many threads for the same program:

here

and here

and here

and here.
Was This Post Helpful? 1
  • +
  • -

#10 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 12 January 2011 - 09:40 AM

Basically, I'd need to include those functions. Why couldn't you access the data by using node->data? My apologies about the multiple posts, feel free to delete the rest mods.
Was This Post Helpful? 0
  • +
  • -

#11 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 12 January 2011 - 10:15 AM

My particular struggle at the moment is getting the append function to work correctly, particularly I'm having problems using a "current" node. In the beginning it has to be *this, but afterwards I'm not sure how to update it to the last new value...
Was This Post Helpful? 0
  • +
  • -

#12 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Self Contained Linked List

Posted 12 January 2011 - 10:21 AM

You need to post the actual, latest version of your code that's giving you trouble.
Was This Post Helpful? 0
  • +
  • -

#13 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 12 January 2011 - 10:36 AM

At the moment I'm attempting to create my Append function from the bottom up to suit my needs. I have no issue attempting to set a newly appended nodes next value because it's always NULL, however the trouble comes when I try to set it a previous node. I cannot use *this after the first append because *this always remains as the root node (I obviously have the same issue setting the next node because I'm unable to set *this next node as the new value.

After much thought and contemplation, it appears understanding how to avoid this issue (no pun intended) is my main hurdle attempting to create this Linked list in the way specified.

	void Append(ListElement &temp)
	{
		ListElement* newNode = &temp;

		newNode->mNext = NULL;
	}

Was This Post Helpful? 0
  • +
  • -

#14 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Self Contained Linked List

Posted 12 January 2011 - 11:14 AM

That's exactly why I suggested in one of your other threads here, that you should keep the mLast pointer as a data member of the class. I didn't write that post just to exercise my fingers. You asked for help, and I thought I was giving you a list of useful suggestions, but you made no indication that you even read the post.

The alternative is to use another (temporary) ListElement* pointer in the Append method and "walk" it through the entire list until it reaches the end (you know you're at the end when mNext == NULL.
For example:
  ListElement* current = this;
  while( current->mNext ) {
    current = current->mNext;
  }


When it drops out of that loop, current will point to the last node in the list.

[Note that "while( current->mNext )" is equivalent to "while( current->mNext != NULL )"]
Was This Post Helpful? 1
  • +
  • -

#15 Aequitas1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 31
  • Joined: 16-September 10

Re: Self Contained Linked List

Posted 12 January 2011 - 11:18 AM

My apologies, I must have missed it amongst all my seperate posts (stupid idea).

This post has been edited by Aequitas1: 12 January 2011 - 11:22 AM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2