Print Friendly, PDF & Email

Singly linked lists are an essential data structure in search tasks and are the gateway to more complex data structures.

As always, there is more than one way to implement these linked lists, here we will try two, the imperative form and the recursive form.

Both forms of implementation start with the approach of the ADT “Node”. If you do not know what an ADT is, I recommend you first check the entry abstract datatype.

A simply linked list node must have an object that stores the information in question and a pointer to a possible Node type object, so that we can relate several nodes one by one.

Implementation

For our implementation, we will generate the standard ways to compare two ADTs in Java which are the Equals and HashCode methods and a method for their textual representation.

It is very important to note that for the implementation of the toString method we only use the information, since in case of circularly connecting the first node with the last one, we will have a memory saturation problem when trying to print all the nodes and do more complex the task of printing, although later I will teach how to deal with this type of problems.

Now let’s make the skeleton of the linked list

Iterative implementation

Possibly the imperative implementation is easier to understand for someone who is starting up.

First we create a method to display a textual representation of our simple linked list and a simple method to add elements to the end of the simply linked list.

Recursive Implementation

The recursive implementation is more closely related to the philosophy of Object Oriented Programming.

First we create a method to show a textual representation of our singly linked list and a simple method to add elements to the end of the singly linked list, in this case the functionality will be delegated to each node to be printed and request the printing of the other nodes and to add or delegate data if the case shows up.

Then we’ll proceed to the implementation on the Node object.

End of Part 1

Radio

Do NOT follow this link or you will be banned from the site!