I've just got onto linked lists, and my book uses all these classes to make it...I take it there is pretty much a standard syntax to make these...can you post it for me please?
What would you want to use linked lists for?
Printable View
I've just got onto linked lists, and my book uses all these classes to make it...I take it there is pretty much a standard syntax to make these...can you post it for me please?
What would you want to use linked lists for?
Basic linked list.
Linked lists are dynamic so nodes can be inserted anywhere in the list much easier than inserting a value in the middle of an array. Linked lists being dynamic also allow it to grow or shrink as needed, which optimizes memory.Code:struct node
{
int value;
node *next;
}
int main()
{
node *listHead;
listHead = new node;
listHead->value = 5;
listHead->next = new node;
}
Structures like trees work on this kind of coding.
Ex:
Objects like Vectors are linked lists and are available in the STL if you don't care how they are coded, but rather just want to use them.Code:struct node
{
int value;
node *left;
node *right;
}
Ok thanks...my book had like 5 classes...node, linked list, internal node etc
Well often for a more comprehensive linked list atleast one class and one struct would be created so that using the linked list would be easier to use such as creation, destruction (important because linked list is dynamic i.e. free memory), adding item, deleting item, finding item, etc.
Ex:
Code:struct node
{
int value;
node *next;
}
class linkedList
{
public:
linkedList();
~linkedList();
insertItem(int);
deleteItem(int);
findItem();
private:
node *head;
}
int main()
{
linkedList phoneNumbers;
phoneNumbers.insertItem(3019854434);
}
Drawback with linked list is that you always have to start at the head or the tail (unless you store the middle element all the time n stuff and kept the list sorted). So the time it takes to find an element in the list depends on the elements place in the list and the size of the list. An array for instance has much faster access to an arbitrary object.
>> Objects like Vectors are linked lists and are available in the STL
vectors aren't implemented with linked lists since they require contiguous storage. The list container is implemented as a linked list.
How would I then output my list and how do I order the information in my list?
To output the info you just go from the head to the tail. To sort the list you do that when you insert....http://www.cprogramming.com/tutorial/lesson15.html is a tutorial on linked list.
Can you give me a full code because Kurisu's doesn't actually compile when added into stuff.
if you just want to use a linked list (as oppossed to writing one yourself) just use std::list.
if you want to learn about linked lists, write your own one, use it for a few days and then compare it to std::list. At that point, you should throw away your implementation and never use it again. :D
>> vectors aren't implemented with linked lists since they require contiguous storage. The list container is implemented as a linked list.
they can be, but aren't usually coded that way (when you think of a vector in terms of concept of access, it doesn't really matter how you implement it ~ just that it conforms to the expected interface). it wouldn't be as efficient at indexing, but it would outperform the usual implementation in other respects.
are you sure about that? I'm fairly certain the Standard requires a vector to have contiguous storage. I don't have the standard in front of me so I can't check, but I'm almost certain that this should be standard-conformingQuote:
Originally Posted by Sebastiani
Code:/* old c interface */
void printIntArray(int* pArray, int size)
{
int i = 0;
for (; i < size; ++i)
{
printf("%d", pArray[i]);
}
}
std::vector<int> foo;
foo.push_back(1);
foo.push_back(2);
foo.push_back(3);
foo.push_back(4);
printIntArray(&foo.front(), foo.size());
>my book had like 5 classes...node, linked list, internal node etc
That sounds like Jesse Liberty being overly complicated with simple concepts again. If not for books like his, people might actually realize that this stuff is pretty easy. When teaching data structures, I prefer to eschew the OO crap because it only serves to hide the concepts under layers and layers of abstraction framework. As you've seen, some authors don't agree.
>I take it there is pretty much a standard syntax to make these
Not really. There are conventions when it comes to the algorithms used, but the interface and implementation are largely up to the author, and dependent on how the list is going to be used.
>I'm fairly certain the Standard requires a vector to have contiguous storage.
Correct.
I would definitely recommend Prelude's tutorials, actually (the sorting and hashtable articles are great). a good reference at any level. :D
>> There are conventions when it comes to the algorithms used, but the interface and implementation are largely up to the author, and dependent on how the list is going to be used.
>> When teaching data structures, I prefer to eschew the OO crap because it only serves to hide the concepts under layers and layers of abstraction framework.
and you see new programmers go wrong there by jumping into such compl(ex|icated) projects before even knowing what a byte actually is, or how to dereference a pointer, or whatever.
>> I'm fairly certain the Standard requires a vector to have contiguous storage.
I see your point, and I understand why the standard went that way on it - but I'm just not convinced that that's production code (why not a templated iterator?) - it's almost like a textbook example...Code:void printIntArray(int* pArray, int size)
why not a templated iterator? because it's a C interface for some huge library you need (Win32 for example).Quote:
Originally Posted by Sebastiani
This thread seems to have moved quite off-topic.
Seeing as you say there are many ways if making linked lists...could someone please just enter a simple program that will compile and show me how to use linked lists and output them.
Here's a link to the FAQ section of this site that provides all you ask for.
http://www.cprogramming.com/tutorial/lesson15.html
It seems easier to do it with classes....Kurisu's way looks like something that I understand...could someone just complete the code for me please.
The first example you were given by Kurisu is a pretty simple, but fully functional linked list. To create the list, the easiest way (IMHO) is to build it in 'reverse' order. By this, I mean, create the last/end node first.. then work your way to the front
Slightly modified version of Kurisu's first example:Since the above code has built the list backwards, by the end of the for loop, current will be a pointer to the node object at the front of the list.Code:struct node
{
int value;
node* next;
node(node* n, int i) : next(n), value(i) {}
};
int main()
{
node* current = NULL;
for (int i=0; i!=10; ++i)
current = new node(current, i);
// Build a list in reverse
}
declare a public member function of the linkedList class to display the data stored within the linked list
within the body of the function definition do something like this:
Code:node * current; //use a temporary node pointer to traverse the list
current = head; //start at the front of the list
while(current != NULL) //assuming there is a value associated with current
{
cout << current->value; //display it
current = current->next; //now go to the next node in the the list
}
If your still looking for a simple example here is something that should compile.
1) Inserts 3 items into a linked list.
2) Displays all items to standard output.
3) Destroys linked list (frees allocated memory)
Of course you can modify this for inserting items anywhere in the list; searching list; etc.Code:#include <iostream>
// THIS SECTION [1] WOULD NORMALLY GO INTO "linkedList.h"
// #ifndef linkedList_h
// #define linkedList_h
struct node
{
int ID;
int phoneNum;
node *next;
// node *prev; Used for a doubly linked list. i.e. traverse both ways.
};
class linkedList
{
public:
linkedList();
~linkedList();
void insertItem(int ID, int phoneNum);
void outputList();
private:
node *head;
// Can add more stuff if desired i.e. int numEntries; node *lastEntry;
};
// #endif
// END OF SECTION [1]
// THIS SECTION [2] WOULD NORMALLY GO INTO "linkedList.cpp"
// #include "linkedList.h"
linkedList::linkedList()
{
head = NULL;
}
linkedList::~linkedList()
{
node *iterator;
while(head != NULL)
{
iterator = head;
head = head->next;
delete iterator;
}
}
void linkedList::insertItem(int ID, int phoneNum)
{
if(head == NULL)
{
head = new node;
head->ID = ID;
head->phoneNum = phoneNum;
head->next = NULL;
}
else
{
node *iterator = head;
while(iterator->next != NULL)
{
iterator = iterator->next;
}
iterator->next = new node;
iterator = iterator->next;
iterator->ID = ID;
iterator->phoneNum = phoneNum;
iterator->next = NULL;
}
}
void linkedList::outputList()
{
node *iterator = head;
while(iterator != NULL)
{
std::cout << "ID #: " << iterator->ID << "\nPhone Number: " << iterator->phoneNum << "\n\n";
iterator = iterator->next;
}
}
// END OF SECTION [2]
// THIS SECTION [3] WOULD NORMALLY GO INTO "main.cpp"
// #include "linkedList.h"
int main()
{
linkedList students;
students.insertItem(1, 2983223);
students.insertItem(2, 1456784);
students.insertItem(3, 4868336);
students.outputList();
return 0;
}
// END OF SECTION [3]
Graphical Representation of above Linked List