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?
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; }
Last edited by Kurisu; 04-25-2006 at 10:32 AM.
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.
STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.
>> 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.
STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.
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.
"I saw a sign that said 'Drink Canada Dry', so I started"
-- Brendan Behan
Free Compiler: Visual C++ 2005 Express
If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?
>> 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.
Last edited by Sebastiani; 04-25-2006 at 06:11 PM. Reason: grammar
Code:#include <cmath> #include <complex> bool euler_flip(bool value) { return std::pow ( std::complex<float>(std::exp(1.0)), std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0) *(1 << (value + 2))) ).real() < 0; }
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-conformingOriginally 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());
"I saw a sign that said 'Drink Canada Dry', so I started"
-- Brendan Behan
Free Compiler: Visual C++ 2005 Express
If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?
>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.
My best code is written with the delete key.
I would definitely recommend Prelude's tutorials, actually (the sorting and hashtable articles are great). a good reference at any level.
>> 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)
Last edited by Sebastiani; 04-25-2006 at 11:00 PM. Reason: code tags, formatting
Code:#include <cmath> #include <complex> bool euler_flip(bool value) { return std::pow ( std::complex<float>(std::exp(1.0)), std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0) *(1 << (value + 2))) ).real() < 0; }
why not a templated iterator? because it's a C interface for some huge library you need (Win32 for example).Originally Posted by Sebastiani
"I saw a sign that said 'Drink Canada Dry', so I started"
-- Brendan Behan
Free Compiler: Visual C++ 2005 Express
If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?