Собственная реализация linkedlist java

Implementing a Custom Generic Linked List in Java

Linked lists are a fundamental data structure used in computer science, and Java provides its own linked list implementation. However, there may be times when you want to create your own custom linked list. Implementing a custom generic linked list in Java can be a valuable learning experience and provide greater flexibility, performance, and an opportunity to practice your coding skills. This article will discuss the benefits of creating a custom linked list and how to implement one in Java.

Benefits of creating your own custom generic linked list

You might wonder why we would create our custom generic linked list even though Java provides a generic linked list that can smoothly perform basic operations. There can be many reasons to do so based on one’s requirements.

• Customization: The built-in Java LinkedList may not exactly meet your needs. For example, you might need a linked list that behaves differently or provides additional functionality.
• Performance: In certain cases, a custom linked list implementation may be more efficient than Java’s implementation. For example, if you have a specific use case that requires a certain data structure or algorithm, you can optimize the implementation for that specific case.

Creating a custom generic linked list

We will create our linked list in a series of steps.

• How to make a generic linked list?
• How to make our internal node structure?
• How to keep track of the head node?
• How to add new nodes in the linked list?
• How to print a linked list?

Let’s look at them one by one.

How to make a generic linked list?

We will use the generic feature of java and make our class in the following way –

As we have used Type T, our class can accept any data type now and make our linked list generic.

How to make our internal node structure?

A Linked List usually comprises a data field and a next field.

• “data” field holds the value, or we can say it contains the actual data.
• “next” field contains the information about the next node, or we can say it points to the next node in the linked list

Below is the structure for the same –

We have made one “Node” class representing a node in the linked list. Node class constructor is a parameterized constructor accepting a single parameter of any data type.

Right now, our Linked List class looks like this –

How to keep track of the head node?

A head node is the first node in the linked list.

After making our linked list class generic and describing the node structure, the next thing is to know how we will keep track of our head node while making a linked list.

We will make a new data member named head of type Node in our Linked List class.

Now, the head variable in our class will keep track of the first node in our Linked List and in this way, we can always access the head node and its content.

How to add new nodes in the linked list?

We know that Linked List is made up of nodes. So, now the question is, how do we add nodes to our List?

We Will make an add() method, which could add the nodes to our list.

• add() method should only have one argument to accept the value to be added in the node.
• It should accept any data type so that our list can be generic.
• And it should add the node at the end of the linked list.

Creating add method

We can make a new Node using the below line of code.

Node node = new Node(element);

Add the newly created node to the Linked List. As the Linked list is empty, so the newly created node will become the head using the code below.

Any more nodes will be added to the end of the Linked List. If a node’s next variable value is null, it means the current node is the last node of the list, and any new node will be added afterwards.

So, we will iterate until the last node and add a new node, as shown by the code below.

Node iterator = this.head; while (iterator.next != null) < iterator = iterator.next; >iterator.next = node;

Note: The above code complexity is O(n), where n is the length of the Linked List. We can optimize it by storing the last node so we don’t have to iterate the whole list to reach the last node. This will make our code run faster and in O(1) complexity.

Here is our final add() method.

void add(T element) < Node node = new Node(element); // adding head node if (this.head == null) < this.head = node; >// adding other nodes else < Node iterator = this.head; while (iterator.next != null) < iterator = iterator.next; >iterator.next = node; > >

How to print a linked list?

We can iterate over the whole list to print the data individually until no node is left.

So, here is our custom generic Linked List, which can add elements and print the whole list.

public class LinkedList  < private Node head; class Node < private T value; private Node next; private Node(T value) < this.value = value; this.next = null; >> void add(T element) < Node node = new Node(element); if (this.head == null) < this.head = node; >else < Node iterator = this.head; while (iterator.next != null) < iterator = iterator.next; >iterator.next = node; > > void print() < Node iterator = head; while (iterator != null) < System.out.println(iterator.value + " "); iterator = iterator.next; >> public static void main(String[] args) < LinkedListintegerLinkedList = new LinkedList<>(); integerLinkedList.add(10); integerLinkedList.add(20); integerLinkedList.add(30); integerLinkedList.print(); LinkedList stringLinkedList = new LinkedList<>(); stringLinkedList.add("Hello"); stringLinkedList.add("Codekru"); stringLinkedList.print(); > >

We have just written functions to add elements to a list and print it to keep our post simple. You can also similarly make methods to remove nodes or print the length of the linked list or any other.

I hope you find this helpful. If you have any doubts or concerns, you can write to us in the comments or mail us at [email protected]

Источник

Custom LinkedList Implementation in Java

In this article, we will be creating a LinkedList implementation in Java and perform several operations such as insert a node at the end, insert a node at a given index, delete a node, insert the head node and traversal of a linked list.

What is LinkedList

Linked list is a linear data structure containing interconnected nodes through pointers. Since there is no concept of pointers in Java, each node holds the reference of another node but the last element of the linked list refers to NULL, meaning the end of the list.

Linked list can grow and shrink in size dynamically without wasting any memory. Hence, we prefer a linked list for quick insertion and deletion, unlike an Array List. A linked list is memory efficient but takes some extra memory for pointers that points to the next node.

Linked List Implementation

As discussed above, linked list is an interconnected node, let us define the node first.

Linked List Node Implementation

Following is the type declaration for a node of a linked list.

public class Node < private int data; private Node nextNode; public Node(int data)< this.data = data; > public int getData() < return data; > public void setData(int data) < this.data = data; > public Node getNextNode() < return nextNode; > public void setNextNode(Node nextNode) < this.nextNode = nextNode; > >

It contains a reference of another node called as nextNode and the data as a member variable which can be of any other data type.

Linked List Declaration

The first node of the linked list is called head and this is the starting point of any linked list. Whenever we want to traverse a linked list we start with the head pointer. Below is our class template for linked list.

public class CustomLinkedList < private Node head; public CustomLinkedList()< >. >

Now, let us start implementing the different operations that can be performed on a Linked list.

Insertion in a Linked List

Insertion can be done at 3 places in a linked list. We can either insert at head, tail or at a particular location.

Insertion at Head and Tail

The method accepts the data and creates a new Node. If this is the first insertion, then the head is null and hence this new node is assigned to head.

Else, we can traverse the list until we reach the last node. The last node will have the next reference pointing to null. Once, we reached the last node, we can assign the reference of new node to the last node. Now, this new node becomes the last node of the linked list which is again pointing to null.

public void insert(int data)< Node newNode = new Node(data); if(this.head == null)< head = newNode; >else < Node currentNode = head; while(currentNode.getNextNode() != null)< currentNode = currentNode.getNextNode(); >currentNode.setNextNode(newNode); > >

public void insertHead(int data)

Insertion at a Particular Node

Traverse to the node where we want to insert the new node. Now, we can set the next node reference of current node as a next node reference of the new node to be inserted and the next node reference of current node as the new node that to be inserted.

public void insertAt(int index, int data) < Node nodeToBeInserted = new Node(data); Node node = head; for(int i = 0; i< index -1; i++)< node = node.getNextNode(); >nodeToBeInserted.setNextNode(node.getNextNode()); node.setNextNode(nodeToBeInserted); >

Deletion of a Node

To delete a node, simply assign the next reference of a particular node to be deleted to the next node reference of the previous node.

public void deleteNodeAt(int index) < Node node = head; for(int i = 0; i< index -1; i++)< node = node.getNextNode(); >node.setNextNode(node.getNextNode().getNextNode()); >

Traversing a Linked List

We can recursively traverse a linked list using while loop untill we reach the last node. The last node of a linked list points to NULL object.

public void display() < if(head != null)< Node currentNode = head; while(currentNode.getNextNode() != null)< System.out.println(currentNode.getData()); currentNode = currentNode.getNextNode(); >System.out.println(currentNode.getData()); > >

Reversing a Linked List

To reverse a linked list, we need 3 pointers — previous, current and next. Initially, current pointer points to the head node and in each iteration, the next node of current node points to the previous node and we shift all the pointers one step ahead, meaning the previous pointer now points to the current node and current pointer points to the next node.

public Node reverse() < Node previous = null; Node current = head; Node next; while (current != null)< next = current.getNextNode(); current.setNextNode(previous); previous = current; current = next; >return previous; >

Check Loops in Linked List

To check for any existing loop in a linked list, we need to traverse every node of the linked list and put the node info in a Map where the key of the Map will be the Node and value can be the count of node present in the linked list. Once, the count is greater than 1 means duplicate node and hence a loop exists in the list.

Below is the Java implementation for the same.

public boolean checkLoop()< boolean loopExists = false; Map&ltNode, Integer&gt map = new HashMap&lt&gt(); Node tempNode = head; while (tempNode != null)< if(map.get(tempNode) == null)< map.put(tempNode, 1); >else < map.put(tempNode, 2); loopExists = true; break; >tempNode = tempNode.getNextNode(); > return loopExists; >

Linked List Runner

Now let us test our linked list implementation with a main class.

public class LinkedListRunner < public static void main(String [] args)< CustomLinkedList customLinkedList = new CustomLinkedList(); customLinkedList.insert(5); customLinkedList.insert(10); customLinkedList.insert(15); customLinkedList.insert(20); customLinkedList.display(); customLinkedList.insertAt(2, 100); System.out.println("********"); customLinkedList.display(); System.out.println("********"); customLinkedList.deleteNodeAt(2); customLinkedList.display(); System.out.println("********"); customLinkedList.insertHead(50); customLinkedList.display(); >>

Conclusion

In this article, discussed about LinkedList implementation in Java and perform several operations such as insert a node at the end, insert a node at a given index, delete a node, insert the head node and traversal of a linked list.

If You Appreciate This, You Can Consider:

About The Author

A technology savvy professional with an exceptional capacity to analyze, solve problems and multi-task. Technical expertise in highly scalable distributed systems, self-healing systems, and service-oriented architecture. Technical Skills: Java/J2EE, Spring, Hibernate, Reactive Programming, Microservices, Hystrix, Rest APIs, Java 8, Kafka, Kibana, Elasticsearch, etc.

Источник