Linked Lists

[S6k9GNh0]

Article based on Linked Lists by computerquip revision 2:

Linked lists are a basic concept in almost all programming languages, including interpreted and higher level languages. All a linked list is is a structure that holds a list of structures containing a way to iterate to the next and/or last object via reference. In C++, we are given an implementation of an advanced doubly linked taking advantage of templates which we call std::list. I will explain what doubly linked means, etc. In C, the standard library does not provide any containers at all, which isn't necessarily bad but this forces you to make your own. The following example will work with both C and C++ (or should):

typedef struct Node
{
   void * data; //Data to be held inside of node
   //In C, one would normally just place a type here.
   Node * next; //Next element of data
};

This is called a singly linked list node since it only holds a single link which happens to be the next link in the list. Commonly, this is all there is to a C list implementation. Some go further though, mainly to build something to make the list a little bit more usable:

typedef struct List
{
   Node * list; //Array of nodes.
   //Node * last; //Sometimes people add a pointer directly to the beginning or end of a list.
};

This struct alone gives access to the first pointer of the linked list, an overall access to the list, and lets the user build whatever he wants on top of it. You'll also find people who create functions like "next()" etc. This is relatively simple to use inside of a main program as well:

//Please note that this does not use the List struct.
//It looks sloppy to use it unless your using a doubly linked list.

typedef struct Node
{
   int data; //We could define an ENUM to choose which type we want, but no point.
   Node * next; 
};

int main(int argc, char ** argv)
{
   Node * nodes = malloc(sizeof(Node)); //Beginning link.
   const int sizeoflist = 5; //5 is random.
   //Don't let this hurt you. When you make a list, it should be obvious when you add elements.
   
   Node * iter = nodes; //an iterator so we don't forget the first link of the chain.
   for (int i = 0; i != sizeoflist; i++) //I don't know if this is right. 
   {
      (*iter).next = malloc(sizeof(Node));
      (*iter) = (*iter).next; //iterate to the next element and reassign.
   }
}

This simply makes a five element list which contains no data. This is just an example though and sizeoflist is unrealistic. You should ALWAYS know when to add elements to the list. If not, then a list isn't the correct container to use.

As you could probably imagine, we could do so much more with C++ classes and templates, it's not even funny:

editing...

[kempofighter]

Hmm, I have a question. Is this a C article or a C++ article? I would have thought that if you are going to write an article on lists where you write your own class that perhaps it would be a C article. In C++ we have the std::list. What is the advantage of showing a user defined list implementation?

I would think that if you are going to show someone how to write a custom list class that you shouldn't use a std container as the underlying container. Either write the thing from scratch or simply write an article on how to use a std::list and why a std::list is sometimes a better choice then a std::deque or std::vector.

[chrisname]

Yes, it is a C article. C is well known for it's classes and containers.

[S6k9GNh0]

C++ doesn't have a standard singly-linked list as far as I know. It's for both. Although I've yet to finish the article and I'm sure most don't care anyways right now. I have a whole stack I'm going to post up on my website one of these days.

[kempofighter]

Okay, well that is a fair point. let me ask you this. What is the advantage of using a custom written singly linked list over the std::list? I would argue that if there is a benefit of it then you should consider writing it completely instead of using a vector as an underlying container. The vector's implementation may defeat the purpose of whatever you are trying to achieve by writing the custom linked list.

[S6k9GNh0]

The more correct way is to hold a pointer to the beginning and end of the list, and then provide functions that iterate in one direction up, or one direction down which defines a singly linked list. A doubly linked list in this case would be more convenient if you need to iterate up and down. I planned on editing this and every single time I begin, I run out of time and end up canceling. I'll probably get to it tomorrow or possibly tonight. The vector is not wrong but it doesn't make the class a list anymore. It makes it some sort of meta-container of a vector and list mixture that is heavier than the two individually and hardly useful...

The purpose of a singly linked list over a double is the use of resources. A singly linked list is is smaller to work with and sometimes faster to work with. I will say however that there is no significant amount of gain here and the only reason I'm attempting to make an implementation is for educational purposes only. It's always good to know the internal and external of whatever you are using.

[chrisname]

Error: in C, a Node* isn't valid. That should be struct Node*.