Why do people write Linked List classes?

Aug 22, 2013 at 8:38pm
I am trying to learn how to use linked lists, and all of the tutorials on how to use them have you building your own class to manage the list. I understand how those classes work, but it seems needlessly complicated, when a little bit of searching in the documentation on this site revealed built in containers to do it for you, namely list and forward_list. Do these not do what I think they do? What am I missing here? Why would you implement linked lists yourself, if the c++ standard library has already done it for you?

Thanks
Aug 22, 2013 at 8:46pm
Each programmer does this that to get some experience and to learn the language.

By the way different languages usually have different realizations and interfaces of lists.:)

Maybe we need some International Standard Committee that will give us rules how linked lists shall be implemented.:)
Last edited on Aug 22, 2013 at 8:47pm
Aug 22, 2013 at 9:06pm
Implementing a linked list is the canonical exercise on pointers and data structures. Nevertheless, the reinvention of the wheel is usually due to either ignorance or learning. :-)
Aug 22, 2013 at 9:28pm
So just to be entirely clear, list and forward_list are perfectly fine to use in place of handmade linked list implementations?

I certainly understand implementing it yourself as an exercise, but nowhere in the various tutorials and explanations that I looked up did they mention the existence of list and forward_list. I had to go documentation searching to find those.
Aug 22, 2013 at 9:35pm
In books you are given the idea of the design of lists. The realization of std::list is more complicated. Moreover before the C++ 2011 standard there was no standard single linked list in C++.
By the way there is yet neither standard double linked list nor single linked list in C.
Last edited on Aug 22, 2013 at 9:38pm
Aug 22, 2013 at 9:41pm
closed account (G309216C)
Linked Lists for beginners is a learning scope\idea but it is also highly used in our OS Kernel to pass on chunks of data at one single given time.

For example functions like ZwQuerySystemInformation , which displays data\information regarding processes use Linked Lists, try learn it it is definitely useful in long coming.
Aug 22, 2013 at 10:44pm
Manual linked lists are also useful when you want reusable nodes, or nodes of variable length:
1
2
3
4
5
6
7
8
9
10
11
12
struct Node{
    Node *next;
    //...
    unsigned length;
    T array[1];
};

//...

assert(n > 0);
Node *node = (Node *)malloc(sizeof(Node) + sizeof(T) * (n - 1));
node->length = n;
Last edited on Aug 22, 2013 at 10:44pm
Topic archived. No new replies allowed.