1.

Solve : C++ linked list HELP!!!?

Answer»

Hi. I'm having trouble understanding how to write a linked list in c++. I have to create one for a school assignment but I cannot figure out how to access certain nodes from the list. I know how a linked list WORKS, but I just get so confused over all the pointer usage and stuff. If someone, anyone, can provide a simple, clear, and easy to understand example of how to implement a linked list, it will be GREATLY appreciated. Thank you
Quote

I know how a linked list works, but I just get so confused over all the pointer usage and stuff.
I also don't understand everything about linked lists, but I can give a good example of how to use them. Probably better than most of the things you may have searched up on google.

Quote
I cannot figure out how to access certain nodes
A linked list is designed to be accessed sequentially, not randomly. If you need to be accessing specific nodes, then an array would be best.

Quote
If someone, anyone, can provide a simple, clear, and easy to understand example
I am designing a programming language and it uses a linked list to store the tokens (words/commands). Here is how I implemented it:

This part creates a structure called program to hold the commands. It has two pointers so that the list can be read forwards and backwards.
Code: [Select]//Double linked list for program
typedef struct program
{
struct program* prev;
struct program* next;
char* data; //CHANGE THIS TO DATA TYPE REQUIRED
};
program *node, *head = 0, *tail = 0;

This part opens a text file and stores the "words" into the linked list.
Code: [Select]//Remove newline char
void choppy(char *s)
{
s[strcspn(s,"\n")] = '\0';
}

int main(int argc, char *argv[])
{
char iobuf[255];
char* ptr;
FILE* fp = fopen(argv[1],"r");
if(fp != NULL)
{
while(fgets(iobuf,sizeof(iobuf),fp) != NULL)
{
choppy(iobuf);
ptr = strtok(iobuf,STR_TAB_SPACE);
while(ptr != NULL)
{
node = (program*)malloc(sizeof(program));
node->next = NULL;
node->prev = NULL;
node->data = (char*)malloc(strlen(ptr)+1);
strcpy(node->data,ptr);
if(head == NULL)
{
head = tail = node;
}
else
{
tail->next = node;
node->prev = tail;
tail = node;
}
ptr = strtok(NULL,STR_TAB_SPACE);
}
}
fclose(fp);
node = head;
//displaylogo();
//interpret();
}
}

Now the following methods can be used to TRAVERSE the linked list. You will have to change the data type from char to whatever the datatype of your linked list is.
Code: [Select]//Movement functions
char* str_forward()
{
if(node)
{
node = node->next;
return node->data;
}
else
return NULL;
}

char* str_backward()
{
if(node)
{
node = node->prev;
return node->data;
}
else
return NULL;
}

char* str_stationary()
{
return node->data;
}

I just realized that aparently returning NULL is bad, you probably should use return 0;A few mistakes I just noticed:

In the method str_forward:
if(node) should be if(node != tail)

In the method str_backward:
if(node) should be if(node != head)

In the main method:
The constant STR_TAB_SPACE should be INITIALIZED like so...
const char STR_TAB_SPACE[3] = {32, 9, 0};the big "mistake" being that your code is pure C, and he wanted C++. Not hugely different aside from the fact that a C++ solution would probably use a class.

That being said, rather the critique I think I will try my hand.

The most common method to create a LinkedList via C++ (or any class-oriented approach, really) is to make a "main" LinkedList class, and then have it hold a reference to a single "Node" class, which acts as the list "head". The Node classes hold references to their Next (and in the case of a doubly-linked-list, Previous) items, and would provide all manner if methods to manipulate and access the contents.

First, the header files:

LinkedListNode.h:
Code: [Select]#pragma once


class LinkedListNode
{
private:
LinkedListNode* Next;
LinkedListNode* Prev;
void* Value;

public:
LinkedListNode(LinkedListNode* pPrev,LinkedListNode* pNext,void* pValue);
~LinkedListNode();
LinkedListNode* getNext();
LinkedListNode* getPrev();
void setNext(LinkedListNode* newnext);
void setPrev(LinkedListNode* newprev);
void* getValue();
void setValue(void* value);


};


BCLinkedList.h
Code: [Select]#pragma once
#include "LinkedListNode.h"
class BCLinkedList
{


private:
LinkedListNode* listhead;
public:
BCLinkedList(void);
~BCLinkedList(void);
void setHead(LinkedListNode* newhead);
LinkedListNode* getHead();
LinkedListNode* getItem(int index);
};

Now, to flesh out the definitions with some actual code!

LinkedListNode.cpp:
Code: [Select]#include "StdAfx.h"
#include "LinkedListNode.h"


LinkedListNode::LinkedListNode(LinkedListNode* pPrev,LinkedListNode* pNext,void* pValue)
{
Next=pNext;
Prev=pPrev;
Value=pValue;


}
void LinkedListNode::setValue(void *value)
{
Value=value;


}
void* LinkedListNode::getValue()
{
return Value;


}
LinkedListNode* LinkedListNode::getNext()
{

return Next;


}
LinkedListNode* LinkedListNode::getPrev()
{
return Prev;


}
void LinkedListNode::setNext(LinkedListNode *newnext)
{

Next = newnext;


}
void LinkedListNode::setPrev(LinkedListNode *newprev)
{
Prev = newprev;



}


and the linkedList class itself:

Code: [Select]#include "StdAfx.h"
#include "BCLinkedList.h"

BCLinkedList::BCLinkedList(void)
{





}



BCLinkedList::~BCLinkedList(void)
{
}
// void setHead(LinkedListNode* newhead);
//LinkedListNode* getHead();
LinkedListNode* BCLinkedList::getHead()
{
return listhead;


}
void BCLinkedList::setHead(LinkedListNode *newhead)
{

listhead = newhead;

}

LinkedListNode* BCLinkedList::getItem(int index)
{
LinkedListNode* usenode = this->listhead;
for(int i=0;i<index;i++)
{
if(usenode!=NULL)
{
usenode=usenode->getNext();
}
else
{
return NULL;

}



}
return usenode;



}








And finally, the main routine that is going to run the above.

Code: [Select]
#include "stdafx.h"

#include "BCLinkedList.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
BCLinkedList ll;
int i=1;
LinkedListNode* firstnode= new LinkedListNode(NULL,NULL,(void*)i);
LinkedListNode* currnode = firstnode;
for(int i=1;i<10;i++)
{
currnode->setNext(new LinkedListNode(currnode,NULL,(void*)i));


currnode=currnode->getNext();

}

ll.setHead(firstnode);

currnode = ll.getHead();
while(currnode!=NULL)
{

cout << ((int)currnode->getValue()) << endl;


currnode=currnode->getNext();




}

LinkedListNode* indexednode = ll.getItem(3);
cout << ((int)indexednode->getValue());


int p=0;
cin >> p;
return 0;
}



First and foremost: do not use this code! I just created it in around 15 minutes. I say don't use it, because I'm ALMOST positive that I should be performing some sort of deallocation- but I'm not. For this short test it's not that important, but if you were to use any of this in an assignment you would probably lose marks. The original question of course was how to access a particular node of the list. this is somewhat vague, but I assume that you mean something like the "getItem()" method I created in my example:



Code: [Select]LinkedListNode* BCLinkedList::getItem(int index)
{
LinkedListNode* usenode = this->listhead;
for(int i=0;i<index;i++)
{
if(usenode!=NULL)
{
usenode=usenode->getNext();
}
else
{
return NULL;

}



}
return usenode;



}
The basic idea is simply to iterate from 0 to the passed index, and in each iteration MOVE forward in the list. There is of course a null check (in case somebody tries to access element 40 of a 10 item list or something). I don't believe it's insulated from corner cases (passing in 1 would probably give the same results as 0, I think, I didn't test it extensively).

The main point here is to show the method used- basically, you use the passed index as an upper bound on a loop you use to go through each item. Note that an optimization method used by double-headed lists (that is, the LinkedList has references to the head tail nodes) is to iterate from the closer side, but that's a special case scenario (also, my implementation is not a two-headed list).


I imagine this same little "indexer" could be used on Linux711's C code. Also I didn't feel like toying with mine to make it an actual indexer (so that one could say linkedlistvalue[3] and get back a LinkedListNode*, this was because to be frank I don't really like C++.

Also the name "BCLinkedList" was chosen because I didn't want to see if LinkedList would conflict with an existing stl class or something.


Discussion

No Comment Found

Related InterviewSolutions