Hello everyone, welcome to our discussion on a new topic🎉. Have you ever witnessed a group of people holding hands to form a chain and stop something? 🤝 For instance, during a protest, the police may surround the protesters, and the protesters will hold hands to form a chain. If one person breaks the chain, the protesters will be able to enter that area. This is similar to a linked list, where the items in the list are connected.🧐 I understand that you may still be confused, but don't worry, I will explain everything step by step😊.
The concept is that various items are interrelated through links. For instance, a train has multiple compartments that are connected from both sides. Without this connection, the train cannot move safely. Any movement, either forward or backward, would result in a crash.
Linked lists work in a way that to access a specific item, we need to know its connection or link with other items. Therefore, if we want to add or remove items from the list, we must ensure that new connections are properly made with the other items when adding new items and that connections are properly broken when removing items.
Imagine you have a necklace made up of several beads. Each bead is unique and important to the overall design of the necklace. However, if one of the beads becomes damaged or needs to be replaced, it's important to do it properly to ensure that the rest of the necklace remains intact.
If you don't handle the situation carefully, you could end up with a necklace that looks uneven or incomplete. This is similar to how improperly breaking the bond between nodes in a linked list can cause errors and issues for the rest of your program.
To replace a damaged bead in your necklace without causing disruptions, you should carefully remove the damaged bead and replace it with a new one that matches the rest of the necklace. It's important to ensure that the new bead is properly secured and that the rest of the necklace is not affected by the change.
In a linked list, you would need to update the pointers to replace a node without disrupting the rest of the list. Similarly, in replacing a bead on a necklace, you need to ensure that the new bead fits seamlessly with the rest of the necklace and that the overall design is not affected by the change.
Overall, properly managing the beads on a necklace and a linked list requires careful attention to detail and a focus on maintaining the overall integrity of the design. By taking the time to handle changes properly, you can ensure that the result is both beautiful and functional. There are different types of linked lists. There are three types of linked lists.
- Singly Linked List
- Doubly Linked List
- Circular Linked List
In this article, we will focus on singly linked lists to uncover their amazing properties.
A singly linked list is a series of items that can only be connected in one direction. Each item in the linked list is called a node, which has two parts: data and the memory address of the next node. By assigning the memory addresses of each node, we can create a link between them and build the linked list. Let's take a closer look at how to visualize a node.
Just think we have a linked list with 2 nodes. The data are 3 and 4 how should we connect. 4 to 3. Let’s see it by illustration.
Because at the start there is no next address. it is null. There is no connection.
In a singly linked list, there are several initializations. Let’s identify those. The first node is called as head in the above example then what should be the head?
Then the node that is currently in the linked list is called current. Then 4 will be the current. In the above for better understanding let’s take the linked list with 4 nodes. 1,2,3, and 4. So it can be illustrated below.
So how can we access the 2nd node? We can access it like a Head.Next. why head. Next?
Because it is the next node after the head node.
Then how should we access the 3d node? Let’s see
So 3rd node can be accessed by the Head.Next.Next
How can we access the current node rather than the current one? It will be Head.Next.Next.
So let’s move on to how to add a new node into the existing linked list. This is called insertion. Insertion can be done in 3 ways.
- Insert at the beginning
- Insert at the end
- Insert at the specific position
Let’s see one by one.
1) Insert at the beginning
In this case, we are going to add a new node in the beginning which means before the head node. So how can we do this? Let’s get the above same linked list and insert the new Node with the data 5. It will look like below.
We should connect the newNode with the head node. For that, the current head node will be the next node after the newNode after inserting. Then the connection can be built as;
newNode.next = head.
To make the newNode as the head node.
So when we add newNode into the beginning we should follow those steps.
newNode.next = head;
head = newNode
2) Insert at the end
This is the easiest insertion in the Linked list when there is only one Node. We don’t have to bother to change the head or another position initialization here. We can simply insert the newNode into the end of the linked list. Let’s see how we do it. Let’s get the same example. Above which got.
I already mentioned that the existing last node will be the current node. But the current node’s next address is null. It means it ends. But it should be the address of newNode. So let’s fix it.
current.Next = newNode
Because the next node of the current node should be the newNode. Then the newNode should be the new current node for that.
Current = newNode
Then it will look like this.
So when we add the newNode into the end we should follow.
Current.next = newNode;
Current = newNode;
3) Insert at the specific position
When we have a newNode, we are asked to insert it into the middle of the linked list. How we can perform that task. Let’s get the same linked LIst we used before and the newNode as the same.
If we are asked to insert the newNode between the 2 and 3. How can we perform?
The node before the newNode should be named as previous. It means when we add the newNode between 2 and 3. We are adding 2 newNode 3. So the node before the newNode should be 2. Then it should be the previous.
Then the 3 will be the previous.Next. So we can break the connection between 2 and 3 and insert the newNode between it.
So we should make the connection with newNode and previous.Next.
OK, what should be to the part of the head and previous nodes?
Let’s make the connection between the previous and the newNode. So it should be Previous.Next = newNode;
It will look like below.
So if we add the newNode at the specific position we should follow.
newNode.Next = previous.Next;
Previous.next = newNode;
As far looked into the linked list and how to add a new node to the linked list. So is it all? The answer is No. Just think if you accidentally add the wrong node to the linked list. Mistakenly or if you want to delete a node that you added earlier. How are you going to do it? Just think of the linked list as a train if we want to the compartment of the train how can we perform? There could be many possibilities. We can remove that compartment from the beginning of the rain, we can remove it from the end of the train and also we can remove specific compartment of the train. So that practical example will be applied here in some way. We can remove the node from the linked list in 3 ways.
- Delete the node at the beginning of the linked list.
- Delete a node at the end of the linked list
- Delete a specific node of the linked list.
Let’s look into it one by one.
1) Delete the node at the beginning of the linked list.
Let’s think about the train. If we are removing the compartment from the beginning. It will be the engine. So if we remove the engine how should the train run? So definitely we have to make the now available first compartment as the engine room. The concept of that will apply here as the same. Let’s see how should we remove the node from the beginning of the linked list. Let’s consider the linked list with 4 nodes as below.
So we are going to remove the node from the beginning.
So if we delete it, what should happen to the head? It will be lost. As the main point, we should remember that the linked list is mainly based on the link between the nodes. If we lose the connection then that node will not be considered. It will be removed from the linked list. So if we want to remove a node from the linked list we should break the connection of that node to others. Let’s look at how we should do it.
To remove the node from the beginning. We should break the connection between the head and Head.Next
So we should assign the head as the Head.Next. Automatically the connection will be loosed and that node will be removed from the linked list.
Let's assign the Head.Next as the head.
Head = Head.next;
So the connection between the first and the 2nd node will be loose automatically. Now the Head is the 2nd node of the linked list.
Finally it will look like this.
2) Delete a node at the end of the linked list
This method is used to remove the last node from the linked list. Let’s take the same example about the train. Just think if we remove the last compartment of the train it won't affect the other compartments. The compartment that is previous to the last compartment will be connected to null when we remove that last compartment. So the same concept will apply here. When we remove the node from the end of the linked list we should remove the connection with that node to other nodes. If we do we can remove that node from the linked list. Let’s see how can we do that. Let’s take the same linked list we used before for an explanation.
So we understood it graphically. So how should we implement it? So here we assign the current as the node before the last node. Then according to the above example, our current is 3rd node. Then simply update the current.next to null then the last node will be removed automatically. That's it!
current.next = null.
So we can remove the node at the end of the linked list.
3) Delete a specific node of the linked list
This will look a little tricky. Here we should consider the two connections when we remove the node. Just think about the same train example. If we are removing the compartment from the middle of the train. We should remove that compartment and connect the compartment before the removed compartment and the compartment next to the removed compartment. So we should apply the same concept here. When we delete a node from the middle, we should make sure to connect the node before it and the node after it. So how can we do that? Let’s see how to proceed with it. For explanation. I will get the same example.
Just think if we are asked to remove node 3 from the linked list. How can we do it? As a first step, we should name the node before the node we are going to remove as previously.
Let’s see how to do it.
So we should write it asl;
previous.Next = previous.Next.Next;
We used previous.Next we should be assigned the node after the previous node So finally, it will look like this,
So now I think that you have a clear idea about the singly linked list and its operations😊. So here we learned about what a singly linked list is and how to add and remove nodes from it under the 3 main ways🤔 . So is it useful to you? Did you get something? Please comment below. Your opinions are more than welcome 😃. Let’s meet with the topic double linked list and circular linked list soon. Happy Learning!🎉
