[phyrrus9]

Making a linked list is easy, incredibly useful, and light on memory.

What you should know:
Basic C
Pointers
Structures

Alright, so what IS a linked list? For the purpose of this tutorial we will call it an automatically resizing array.

So, a linked list has the following:
A head
A tail
nodes

The head is simply the first (0th) node in the list
The tail is the last node in the list (this is where new items will be added)
The nodes are what stores the data and keeps the list together. A node will be a structure consisting of the following:
The data
A pointer to the next node

The definition will be the following:

Code:

struct LLNode
{
     int data;
     struct LLNode *next;
};

data is where we will store our items, we will be using ints for data here.
next is a pointer to the next node in the list

And our actual list type will be defined as:

Code:

struct LLType
{
     struct LLNode *head;
     struct LLNode *tail;
};

Now, we need to have a couple basic functions:
LLInit - sets up our list so we don't have any issues
LLInsert - to add a new item to the list
LLGet - to get an item from the list
LLCount - returns the number of items in the list (optional)
LLRemove - deletes an item from the list (this one is tricky)
LLFree - deletes all nodes from the list

For all of these functions, we will need to pass in a pointer to our LLType object, so that they know what list we are working on.

init, count and free will take only the list as arguments
insert will also take a data object of type int and it will add it to the end of the list
get will take the index of the list and return the object (like array subscripting a[i])
remove will take the index of the element to remove

Okay, let's write up our header:

[code]
struct LLNode
{
     int data;
     struct LLNode *next;
};

struct LLType
{
     struct LLNode *head;
     struct LLNode *tail;
};

void LLInit(struct LLType *list);
void LLInsert(struct LLType *list, int in_data);
int LLGet(struct LLType *list, int index);
int LLCount(struct LLType *list);
void LLRemove(struct LLType *list, int index);
void LLFree(struct LLType *list);

And now, we can start writing the code.

---

LLInit
Apart from previous tutorials, we won't do ANY allocation in init, we will just make sure that the other functions know the list is empty by setting head and tail to NULL

Code:

void LLInit(struct LLType *list)
{
     list->head = list->tail = NULL;
}

---

LLInsert
For insert, we will simply add a node to the tail of the list (specifically tail->next). But there is a scenario we must check for. if tail == NULL. In this case there are no elements in the list (since tail = head iff tail == NULL).
If we run into this scenario, we simply set tail and head to the new node and call it good.
If we don't have this scenario, then we just set tail->next to the new node and then update tail to be that node.

Code:

void LLInsert(struct LLType *list, int in_data)
{
     struct LLNode *newnode = malloc(sizeof(struct LLNode)); //create a new node
     newnode->next = NULL; //initialize the next pointer, we always use NULL to indicate there is not another node following
     newnode->data = in_data; //set the data

     //okay, now we can do our scenario check:
     if (list->tail == NULL) //you can also check for list->head but it isnt necessary
     {
          list->head = list->tail = newnode;
     }
     else //did not catch that scenario
     {
          list->tail->next = newnode; //make the tail have a node following it.
          list->tail = newnode; //update the end of the list marker to the last node
     }
}

That might be a little tricky to understand, but I hope the comments will describe most of it.
The question "why didnt you free newnode?" comes up. Well, we don't want to free it in insert, since we want it to stay in the list. We will free all of these up in LLFree.

---

LLGet
LLGet is actually really simple. But there is one scenario we should check for. What if there is only one item in the list and item 4 is requested? I believe that the program should segfault and crash, but if you don't believe that, here is a snippet of code you can add to the top of the function to cause it not to crash:

Code:

if (LLCount(list) > index) return 0;

Anyways, this one is really quite simple. I will explain it in the code

Code:

int LLGet(struct LLType *list, int index)
{
     struct LLNode *n = list->head; //keep a placeholder
     int i; //for our loop
     for (i = 0; i < index; i++, n = n->next);
     /* now, the n=n->next part is a little tricky. All it means is every iteration of the loop,
          we should move our placeholder one index over. */
     return n->data;
}

Once again, we don't free n because that would cause issues with the list later. This is not a memory leak.

---

LLCount
This one looks almost identical to LLGet, so I will just give you the code for it.

Code:

int LLCount(struct LLType *list)
{
     struct LLNode *n = list->head; //keep a placeholder
     int i; //loop counter
     for (i = 0; n != NULL; i++, n = n->next);
     return i;
}

A little more tricky, but basically our exit condition is when we hit a node that does not exist. Every iteration we increment i (which is our count), and move the placeholder over.

---

LLRemove
This is where it gets tricky, for this I will write us a helper function. This will be a modified form of LLGet that returns the node itself instead of the data:

Code:

struct LLNode *p_LLGet(struct LLType *list, int index)
{
     struct LLNode *n = list->head; //keep a placeholder
     int i; //for our loop
     for (i = 0; i < index; i++, n = n->next);
     /* now, the n=n->next part is a little tricky. All it means is every iteration of the loop,
          we should move our placeholder one index over. */
     return n; //return the node address, not the pointer
}

For remove, we need to do the following:
Locate the node to delete
Save the address of the node
Set the preceding node's next pointer to the node's next pointer (so the list will skip the deleted node)
Delete the node

There is one scenario to check for. If they delete node 0, it will not have a parent. In this case we just set head to node->next and delete the node.

Code:

void LLRemove(struct LLType *list, int index)
{
     struct LLNode *delNode, *prevNode;
     if (index == 0)
     {
          delNode = list->head;
          list->head = delNode->next;
     }
     else
     {
          delNode = p_LLGet(index);
          prevNode = p_LLGet(index - 1);
          prevNode->next = delNode->next; //cause a skip
     }
     free(delNode); //clear up the allocated node
}

That one is where it gets complicated. Since I am not writing a tutorial on concepts, you should read up on linked list functionality if you don't understand it, I am just writing a tutorial on how to program one.

---

LLFree
For simplicity, we will do this one using a for loop. We need to start at the tail node and free up each node backwards (so we can keep track of it).

Code:

void LLFree(struct LLType *list)
{
     int num = LLCount(list);
     struct LLNode *delNode;
     for (i = count - 1; i >= 0; i--) //work backwards through the list
     {
          delNode = LLGet(list, i);
          free(delNode);
     }
}

For those of you who like to do it another way, you are more than welcome to post your code and I will add it to this tutorial.

---

Full code

LinkedList.h

Code:

struct LLNode
{
     int data;
     struct LLNode *next;
};

struct LLType
{
     struct LLNode *head;
     struct LLNode *tail;
};

void LLInit(struct LLType *list);
void LLInsert(struct LLType *list, int in_data);
int LLGet(struct LLType *list, int index);
int LLCount(struct LLType *list);
void LLRemove(struct LLType *list, int index);
void LLFree(struct LLType *list);

LinkedList.c

Code:

#include "LinkedList.h"
#include <stdlib.h>

void LLInit(struct LLType *list)
{
     list->head = list->tail = NULL;
}

void LLInsert(struct LLType *list, int in_data)
{
     struct LLNode *newnode = malloc(sizeof(struct LLNode)); //create a new node
     newnode->next = NULL; //initialize the next pointer, we always use NULL to indicate there is not another node following
     newnode->data = in_data; //set the data

     //okay, now we can do our scenario check:
     if (list->tail == NULL) //you can also check for list->head but it isnt necessary
     {
          list->head = list->tail = newnode;
     }
     else //did not catch that scenario
     {
          list->tail->next = newnode; //make the tail have a node following it.
          list->tail = newnode; //update the end of the list marker to the last node
     }
}

int LLGet(struct LLType *list, int index)
{
     struct LLNode *n = list->head; //keep a placeholder
     int i; //for our loop
     for (i = 0; i < index; i++, n = n->next);
     /* now, the n=n->next part is a little tricky. All it means is every iteration of the loop,
          we should move our placeholder one index over. */
     return n->data;
}

int LLCount(struct LLType *list)
{
     struct LLNode *n = list->head; //keep a placeholder
     int i; //loop counter
     for (i = 0; n != NULL; i++, n = n->next);
     return i;
}

struct LLNode *p_LLGet(struct LLType *list, int index)
{
     struct LLNode *n = list->head; //keep a placeholder
     int i; //for our loop
     for (i = 0; i < index; i++, n = n->next);
     /* now, the n=n->next part is a little tricky. All it means is every iteration of the loop,
          we should move our placeholder one index over. */
     return n; //return the node address, not the pointer
}

void LLFree(struct LLType *list)
{
     int num = LLCount(list);
     struct LLNode *delNode;
     for (i = count - 1; i >= 0; i--) //work backwards through the list
     {
          delNode = LLGet(list, i);
          free(delNode);
     }
}

---

Sample:

Code:

#include "LinkedList.h"

int main()
{
     struct LLType list;
     LLinit(&list);
     LLinsert(&list, 4);
     LLInsert(&list, -1);

     LLGet(&list, 1); //will be -1
     LLGet(&list, 0); //will be 4

     LLRemove(&list, 0); //remove the 4
     LLGet(&list, 0); //will be -1

     LLFree(&list);

     return 0;
}

[phyrrus9]

Any other comments on it or did you just want to get a post count increment here. Your post lacks meat. Its like going to KFC and ordering a bucket of chicken but having them ONLY include the bones.

[panther.]

Any other comments on it or did you just want to get a post count increment here. Your post lacks meat. Its like going to KFC and ordering a bucket of chicken but having them ONLY include the bones.

I have no comment on the thread itself but this was a really, really fucking stupid analogy. Please never use this again.

[phyrrus9]

Okay, back on topic. Does anybody have a comment on the thread? Anything they would like to see?

[Reiko]

Good implementation.

As for something I'd like to see, how about a doubly-linked list?

[phyrrus9]

Doubly linked list it is. It would be neat to write a tutorial on how to turn a binary tree into one