Linked List Tutorial: – Getting Started With Dynamic Data Storage

Linked lists can be a valuable tool when having to structure different data sets and organize linear information for a program. They are commonly used as a replacement for an array because they have certain benefits to using them.

At its core, a linked list is a simple data structure that holds a sequence of nodes. Each node has its own data, plus a pointer to another node. In fact, they’re often taught in order to get students comfortable with pointers.

Below you’ll learn what linked lists are, why they’re valuable, and how to create them. We’ll also offer a few additional resources to help further your education.

What Are Linked Lists?

Put simply, a linked list is an ordered collection of data. It’s meant for linear data structures and is one of the easiest dynamic data structures to implement. Each data element is called a node and contains a single value and a pointer to the next node in the list. If the pointer has a NULL value, then that node is the last in the list.

To help grasp the concept here’s an example outside of computer technology:

Say you’re rating every person in an office based upon typing speed. Your list would begin with Ann because everyone knows she is the fastest – you can hear the sound coming from her cubicle. She’s been told the next fastest person is Steve. Steve knows that his typing speed is close to Ann’s, but not quite as good. He also knows that Karen is almost as fast as he is, but not quite. The list can then continue in this manner. Each member possesses unique information, plus an indicator to who’s the next fastest typist.

Since nodes exist independent of one another, except by the pointer relationship, it is very easy to add, delete, and move them.

Types of Linked Lists

There are a few different types of linked lists. A single linked list, a doubly linked list, a multilinked list, and a circular linked list. We explore each in more detail below. With linked lists, you can perform insertion, deletion, and traversal operations.

1. Single Linked List

A single linked list is a collection of data objects that are linked together by certain references from one object to the next. These objects are often referred to as nodes. Each node will contain at least a single data field and a reference to the following node. Single linked lists are accessed via the first node and can be traversed until the end of the list.

2. Doubly Linked List

Doubly linked lists have two references per each node. The references point towards the next node, and the previous node. With this structure, you have two-way access to the data set, and it offers you more flexibility and speed, because you can navigate your list both directions.

3. Multilinked List

Multilinked lists are general linked lists that have multiple additional lists from a certain node. The new lists can be in any of the styles mentioned here. This style of list can be helpful for sorting a list that’s broken down by the user’s name and age. Or, other styles of data sets where each data point has further classifications.

4. Circular Linked List

The final type of linked list is called a circular linked list. Instead of the final node having a NULL command it will reference back to the head of the list. The structure of the list is similar to the options above.

Why Linked Lists Are Important

Linked lists are useful, because of their dynamic nature. In a computing sense, it only allocates memory when required. So, if you have an application that requires frequent resizing, deletions, insertions, and data updates, then a linked list will be perfect.

Linked lists are commonly used in order to implement graphs, stacks, queues, and other similar programs. With a linked list you can insert items anywhere in the list. Plus, you don’t need to know the size of the final list in advance. It can increase or decrease in size as you see fit.

The easy insertion and deletion is a major advantage to linked lists. For example, you could use an array, but arrays only let you add and remove the last object in the sequence without moving a bunch of data to create a open slot. Linked lists allow for easy sequential data set manipulation, without putting a huge strain on memory resources.

Most Computer Science programs continue to teach students how to implement linked lists, as a solid introduction to dynamic data structures you might want to use in real programs. Plus, even if you never end up using a linked list it’ll provide you with enough understanding to use pointers. You’ll surely be using pointers in a lot of your real-life programs.

Linked List Disadvantages

Linked lists are great for creating an easy-to-modify list. However, they aren’t the perfect solution for every program, as you’ll see below:

1. Linked lists don’t offer a random access point. In order to reach a certain item in your list you must iterate over every item in the list up until that point.
2. The code can get a little complicated because both dynamic memory allocation and pointers are required for the code to function.
3. The total overhead for a linked list can be higher than an array, because the lists are dynamically allocated.

All that being said, knowing how to use linked lists will help you master the use of pointers and have a greater understanding of dynamic data sets as a whole.

Linked Lists Tutorial

Below you’ll learn how to create and implement a basic linked list. We’ll begin with creating a single linked list and it’s nodes, and show how to delete and insert new nodes.

Creating a Node Structure

A linked list consists of several nodes, so we’ll need to create a structure that defines a node. This will need to include at least one variable for data and one pointer to refer to the next node. For our purpose, we’ll stick to our typing speed example and use the person’s name and speed and our data. In C, the data would be defined in a structure as so:

struct node {
    string name[32];
    int speed;
    struct node *next;
}

The important thing here is the next pointer, which is what allows us to work our way through the list.

Creating a Linked List

Now, we’ll need to create a list, which is really just creating the first node. So we define it, allocate enough memory for a single node, and set the next pointer to NULL so we know this is the end of the list. You also set the head pointer to it because this is where the linked list starts.

Then you can fill-in the information for this node: the name of the employee and their typing speed.

Inserting a Node

With our basic list created we can now begin adding elements to the list. So suppose you started with Karen who has a typing speed of 58 words per minute. Next you want to enter Steve with a speed of 63. You would create a node for him and fill in the data. Then you would search through the linked list, but in this case, there would only be one element. You would note that Steve has a faster typing speed, so you would set his next pointer to Karen’s pointer. Since Karen’s pointer is also the head pointer, you would make head point to Steve’s node.

Now you have the linked list starting with Steve’s node. It’s next would point to Karen’s node. And Karen’s node would point to NULL, indicating that her node is the last in the list.

If an employee were hired with a typing speed between Karen and Steve, a node would be created for them. But then Steve’s next would point to the new employee, and the new employee’s next would point to Karen’s.

On the other hand, if an employee were hired with a typing speed less than Karen’s, a node would again be created for them. But then Karen’s next would point to the new employee, and the new employee’s next would point to NULL.

Deleting a Node

Deleting a node from a linked list is actually quite an easy process. We would make the next pointer of the employee ahead of the employee we want to delete point to the employee after the employee we wish to delete. We would then release the memory of the deleted node or we would end up with a memory leak.

Of course, there’s a lot more you can do with linked lists. If you’re interested in exploring linked lists even further, then check out the resources highlighted below.

Linked List Resources

Once you understand the basic concept of linked lists it’s time to grow your knowledge. Below we offer a few additional resources to help to truly master linked lists and gain a deeper understanding of data structures:

• Data Structures and Algorithms Made Easy (2016) by Narasimha Karumanchi: a great book on data structures that will take you far beyond linked lists.
• Linked Lists Basics (PDF): this 26 page PDF will provide you with just about everything you would ever want to know with pseudo-code and C language examples.
• A Gentle Introduction to Data Structures: this simple introduction will take you all the way through creating your first linked list program.
• Linked List Tutorials: this is a collection of 7 short videos on creating linked lists in C++.
• Learn-C.org Linked lists Page: this page walks you through creating a simple C language linked list.
• Data Structures with Javascript: learn linked lists right inside your browser with this JavaScript tutorial.

Summary

Linked lists offer a great concept and practical method of managing and creating dynamic data sets. Hopefully, the information above has helped you grasp and implement a basic linked list, and you will move forward from there.