Code|Beta

Linked lists can be a hassle for a beginner, I’ve tried to simplify this by making a short tutorial on using linked lists using structures (struct) in C++.

I’ve been using linked lists in my programs for a while now. I mostly program in the Object-Oriented method, but one thing I haven’t been able to master is the linked lists using OOP. So what I do is use structures (struct) in order to accomplish this task, now doing this is rather simple.

First we must know what a struct is:

“A structure is a colection of one or more types of elements denominated members“

For example:

struct album{
std::string albumName;
int amountOfSongs;
};

As we can see in the example above, the struct can contain different data types. In order to use the struct and be able to assign the values to it’s members we would:

album a1;

a1.albumName = “Industrial Music”;

a1.amountOfSongs = 15;

So now a1 is an instance of album.

Now that we know what a structure is and how to use it, we can move on to creating a linked list:

What’s a linked list?

“… a linked list is one of the fundamental data structures used in computer programming. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references (”links”) pointing to the next and/or previous nodes…” -Wikipedia

First we must create the struct, this can be done in the header (.h) file of the class, it should go before the declaration of the class:

struct album{

std::string albumName;

int amountOfSongs;

album *Next; //This points to the next node in the linked list

};

class cdColection{

private:

album *Head; //This points to the first node in the list

unsigned int nodeCount;

public:

cdColection():Head(NULL) {nodeCount = 0;};

…

};

As you might have noticed in the past example there are some important things that must be pointed out:

• The struct needs a member that points to itself, in the example above this is the album *Next
• You need something that will point to the first node in the linked list, this would be the head and it must be declared as a global pointer. If the value of this pointer gets lost you will not be able to access the linked list since you have no way of telling the application where the linked list starts.
• When the class is initialized, the Head must be pointing somewhere this it why in the constructor of the class you see Head(NULL) which is the equivalent of doing Head = NULL in the constructor of the class. This way the Head pointer is pointing to something, even if it’s to NULL.
• Since the program is unable to keep a count of how many nodes the linked list has then you will need to maintain a counter, in the example above this is represented by the global variable nodeCount

To create a node in the linked list the class will need a method like the one bellow:

void addNode(std::string name, int songCount){album nAlbum = new album;nAlbum->albumName = name;nAlbum->amountOfSongs = songCount; nAlbum-Next = Head;

Head = nAlbum;

nodeCount++;

}

Now in the example above the new node will always be inserted in the first position, meaning that if I had a table like the one bellow:

Adding another node would make all the other nodes move and add the new node at the top, so the table would look like:

This is the easiest way of adding nodes to the linked list, unless you want to keep another pointer that always points at the Tail of the linked list, then all the nodes you add can be added at the end of the list. You could also add a node in any part of the linked list by simply changing the values of the pointers in the necessary nodes.A graphical view of this linked list would be something like:p

This is a quick simple way to use linked lists in a program, I use this or a similar method in the source code of my projects where a linked list is needed.

-LMurillo

[NOTE: Sorry if you have a double post, there was a tag in the HTML code that was causing an error in the page and it had to be fixed. Apologies for the inconvenience]