Locked [C] Linked List

[Breaker]

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:

 

[LENGUAJE=c]struct LLNode

{

int data;

struct LLNode *next;

};[/LENGUAJE]

 

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:

 

[LENGUAJE=c]struct LLType

{

struct LLNode *head;

struct LLNode *tail;

};[/LENGUAJE]

 

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)

remove will take the index of the element to remove

 

Okay, let's write up our header:

 

 

[LENGUAJE=c]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);[/LENGUAJE]

 

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

 

[LENGUAJE=c]void LLInit(struct LLType *list)

{

list->head = list->tail = NULL;

}[/LENGUAJE]

 

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.

 

[LENGUAJE=c]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

}

}[/LENGUAJE]

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:

 

[LENGUAJE=c]if (LLCount(list) > index) return 0;[/code]

 

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

 

This is the hidden content, please

• Sign In
• or
• Sign Up

{

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;

}[/LENGUAJE]

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.

 

[LENGUAJE=c]

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;

}[/LENGUAJE]

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:

 

[LENGUAJE=c]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

}[/LENGUAJE]

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.

 

 

[LENGUAJE=c]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

}[/LENGUAJE]

 

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).

 

[LENGUAJE=c]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);

}

}[/LENGUAJE]

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

 

[LENGUAJE=c]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);[/LENGUAJE]

 

LinkedList.c

 

[LENGUAJE=c]#include "LinkedList.h"

#include

 

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);

}

}[/LENGUAJE]

 

Sample:

[LENGUAJE=c]#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;

}[/LENGUAJE]

Edited January 6, 2015 by HoRSe
Delete labels [CODE] + Add labels [LENGUAJE=c]