The Linked List is a data structure in which items are not located in contiguous memory. Instead, each element points to the next one.
In some of the programming languages, there is a built-in Linked List data structure, despite this, we can create our own data structure. If we create a custom Linked List, we will be able to edit it as we want.
In general, Linked List has three types:
- Singular Linked List — This is the most basic form of the Linked List. Basically, each node in the Linked List has a reference for only the next node.
- Doubly Linked List — In this version, each node also has a reference to the next node. Besides that, each node has a reference for the previous node.
- Circular Linked List — This is almost same with the Singular Linked List, but the last node of the Linked List must point to the head of the Linked List. That’s why it is called Circular Linked List.
In this blog, we are going to learn the Singular Linked List. The logic is the same in all of them. So, if you learn the Singular Linked List, you will understand the others easily.
Visualizing Linked List
To understand Linked Lists, let’s try to visualize it:
First of all, as you can see from the image, we have 3 nodes. All of the nodes have data and next node’s memory address.
Let’s see them one-by-one:
- First node’s data is 2 and shows the second node’s memory address
- Second node’s data is 3 and shows the third node’s memory address
- Third node’s data is 8 and has a null as a next pointer because it is the last node of the Linked List so that it needs to point to the null
Besides them, we have 2 pointers which are called
tail. Linked List can’t exist without them. Let’s see what they are:
headpoints to the first node of the Linked List
tailpoints to the last node of the Linked List
As we have learnt some basics of the Linked List, let’s dive into the coding for implementing them.
Coding Singular Linked List
To create a Linked List, We first need to understand the basics of Classes and Objects. So, before continuing, go and check this blog.
Note: In this blog, I am using C# language, but once you understand the concept, you can implement it in whatever language you want
Creating Node Class
To start, we first need to create our Node class. Each node in the Linked List will be created by using this class. It will hold information about the node’s data and the next node. Let’s have a look at it:
Firstly, we declare a public
int variable for the node’s data, then
Node variable for the next node.
Secondly, in the constructor, we assign the value parameter passed to this constructor, to the class’ data variable. Then we set its next node to the null.
When we create a new node we will use this constructor.
For example, let’s say we have created a new node with the value of 25:
Node newNode = new Node(25);
It will look like this:
Creating Linked List Class
We created our Node class and now we will create our Linked List class. This class will do everything by using the Node class. This is how it should look like at the beginning:
It will have three variables:
int size for holding current size of the Linked List. We also have a property
Size for getting
size's value outside of the class. We made its set property private, so that it can only be set inside the class.
Node head for pointing to the first node of the Linked List,
Node tail for pointing to the tail of the Linked List.
Then in the constructor, we are setting head and tail pointers to the
null, because we do not have an item in the linked list at the beginning.
With all of these codes, our program should look like this:
To summarize, we first understood what the Linked List is and how is it visualized. Then, we created
In the next article , we will learn how to create methods for
LinkedList to start actually using it. I hope you enjoyed it.
To get to the second part: