Is this your first foray into data structures and are you stumped around the concept of Linked Lists? This short article will cover everything you need to know to get started with using Linked Lists in your programs

What is a data structure?

Data structures are ways you can organize your data in order to use it effectively. With data, it can be of many types, strings, int, float and its important that we use the best possible data structure to make the program run with the best time and space requirements.

What are Linked Lists?

Linked Lists are a type of Data Structure in which elements consist of a series of nodes.

Each node has two items, a data field, and a pointer to the next node.

When you visualize Linked Lists, think of a chain. Each chain link is linked to the next.

There are two main types of Linked Lists, we will learn more about them:

• Singly Linked List: This type of Linked List only has link to the next pointer at any given node. There are no pointers to the previous node from a given node.

• Doubly Linked List: This type of Linked List has a link to both the previous and next pointer from a given node.

Structure of a Singly Linked List

Structure of a Doubly Linked List

In Linked Lists, the main thing you will use to refer to or reach elements is the head pointer. The head pointer points to the start of the list and will be used to traverse the list and reach the other nodes.

Unlike arrays, you cannot access a node in a Linked List by just using its index and referring to it. This adds to the time complexity which we will explore in the next section.

Linked Lists in C++

The Node Class:

class Node {
int data; 
Node *next; 
Node(int val): data(val), next(NULL){};
};

Time Complexity and Big Oh

With Linked Lists, to add an element to the front, you can do so with ease in O(1) time. This is because you only need to modify the new elements next pointer to point at the old starting point. Following that you need to modify head to point to the new element.

For accessing an element in the Linked list, you will have to traverse the list starting at the head till you reach an element. Due to this the time complexity will be O(n) time.

The case will be the same for inserting in the middle and deletion from the middle or end of the list.

What next?

Now that you have a brief overview of linked lists, it's time to explore further with materials online! If you have any questions on the current content, please feel free to mention in the comments below.