Implementation of LinkedList
Tags: linkedlist, dsa, java, javascript
Published: 2023-11-05 12:07:09

Hey Everyone!!!, Hope! Everyone is doing great.

In this Article, We will see how we can implement our own LinkedList class and use them. In this Article, I'm using java but you can use whatever language you comfortable with.

**Prerequisites** :- You must be familiar with the **Object** and **class**.

We defines a simple implementation of a Node class within an Implementation class. The Node class represents a basic node in a linked list data structure, containing an integer data value and a reference to the next node in the sequence.

**Here the term** Reference means address of next node in the sequence. As you can see below


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bz49v3q8y0g43t55616o.jpg)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t42lqvxu7mqxdu65rqrh.jpg)

## Defining a Node Class  (Important)

It is mandatory to Remember this every time we use node type to create node variable. The above code is basic building block of LinkedList Implementation.

1 -The code defines a Node class within an Implementation class, representing a basic unit for a linked list data structure.

2-The Node class consists of an integer data field to store data and a next field to hold the reference to the next node in the linked list.

3-It includes a single-line constructor that initializes the data field of the Node with the value passed as an argument. The next field is not explicitly initialized and defaults to null.

This Node class forms the foundation for implementing linked lists in Java and can be extended for various data structure and algorithm implementations.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h4rw2eke67utruoixv4f.png)

## Defining a LinkedList class 

As we define the child node class above after that we define another child named LinkedList.

**Initialization**

Initialize then node head, tail with null and size with integer. 

Initialize value with null means when there is a single node in the list it always point to the null and last node of list also always point to the null. If node is not pointing anywhere then it is point to null.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vdgt26du90kxpgd9bmpy.png)


**Defining Methods in LinkedList**

**InsertAtEnd Method**

1- A method called insertAtEnd in a linked list implementation that adds a new node at the end of the list.

2- It creates a new node with the provided value and checks if the linked list is empty.

3- If the list is empty, the new node becomes the head of the list; otherwise, it is appended to the current tail node.

4- The tail pointer is then updated to the newly added node, ensuring it always points to the last node. Additionally, the size of the linked list is incremented to reflect the addition of the new element.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ribx3wu9md2jfjbiisl6.png)

**display Method**

1- Method named display within a linked list implementation that prints the elements of the linked list.

2- It initializes a temporary node temp with the reference to the head of the linked list for traversal.

3- The method employs a while loop to iterate through the linked list until the temporary node temp becomes null, ensuring all elements are printed.

4- Within the loop, it prints the data of the current node followed by a space, allowing the elements to be displayed horizontally.

This display method facilitates the visualization and confirmation of the elements stored in the linked list, enabling users to verify the list's content and structure.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zsn81bxo3rjfgce3iu1b.png)

**getAt Method**

1- A method named getAt within a linked list implementation, allowing retrieval of the data value of a node at a specified index.

2- It includes a check to ensure that the provided index is within the valid range of the linked list. If the index is outside the valid range, it prints a "wrong index" message and returns -1.

3- The method initializes a temporary node temp with the reference to the head of the linked list.

4- It employs a for loop to traverse the linked list, moving from the head node to the node at the specified index, determined by the loop counter.

5- The method returns the data value of the node at the specified index if the index is valid, enabling the retrieval of specific data from the linked list.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mcbpsq2jto3z33wd819w.png)

**insertAtHead Method**

1- Method called insertAtHead in a linked list implementation, used to add a new node with the specified value at the beginning of the linked list.

2- It creates a new node with the provided value, initializing the temp variable.

3- If the linked list is empty (i.e., head is null), the new node becomes both the head and the tail of the list, signifying the first and only node in the list.

4- If the list is not empty, the new node is inserted at the head, with its next pointer referencing the previous head node, ensuring the continuity of the list.

This insertAtHead method effectively adds a new node at the beginning of the linked list, updating the necessary pointers and maintaining the list's integrity and size.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c6a2wbd0a4lptxig689d.png)

**insertAt Method**

1- The insertAt method is used to insert a new node with the specified value at the given index in the linked list.

2- It begins by creating a new node t with the provided value and initializes a temporary node temp with the reference to the head of the linked list.

3- If the index is equal to the size of the list, the method delegates the task to insertAtEnd to add the new node at the end of the list, and if the index is 0, it delegates the task to insertAtHead to add the new node at the beginning of the list.

4- If the index is outside the valid range of the list, the method prints a "wrong index" message and returns.

5- If the index is valid and not at the beginning or end, the method traverses the list to the node just before the specified index.

6- It then inserts the new node t at the specified index, adjusting the pointers to maintain the list's integrity, and increments the size of the list.

This insertAt method enables the insertion of a new node at the specified index in the linked list, handling various edge cases and updating the necessary pointers to ensure the list remains intact.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ck0o6whokr7qjxz2oofk.png)


**deleteAt Method**

1- The deleteAt method is used to remove the node at the specified index in the linked list.

2- It initializes a temporary node temp with the reference to the head of the linked list.

3- If the index is 0, indicating the deletion of the first node, the method updates the head to point to the next node, effectively removing the current head. It also decrements the size of the list and then returns.

4- If the index is not 0, the method traverses the list to the node just before the specified index.

5- It adjusts the pointers of the nodes to skip over the node at the specified index, removing it from the linked list. The tail is also updated to point to the new last node.

6- The size of the list is decremented to reflect the removal of the node.

This deleteAt method effectively removes the node at the specified index from the linked list, updating the necessary pointers and adjusting the size of the list accordingly.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/02epnq6q4ubek3uqrgf0.png)