Linked List: The MyLinkedList Implementation

Activity Description

Content

A linked list is a data structure composed of connected Nodes. Each node contains two items:

1. A data, also known as the item interested in adding; can be an int, a string, or even an object.

2. A next, which is also a Node. This is the “link” that connects one node with another node

Beyond Arrays

Arrays are limited based on the capacity provided. E.g., once you define the array's capacity we are “stuck” with that capacity until the program finishes. Therefore, we need another data structure that permits us to “grow” and “shrink” our data as we need. 

The Node

The node is a small data structure that is used only in the linked list context

The node is composed of the value and the next. The value is the actual data that we are interested in storing. The next is the connection between nodes. The value data type can be anything you would like to store. Since the next is the connection between nodes, its data type is Node. I know what you are thinking, “How can we have a data type of something that we are defining”. This sounds a little bit crazy (or recursively), but if you think about it, the connection between nodes requires similar data types. Therefore, the “bridging” between nodes should be Node. 

The node looks as follows:

public class Node{

  String value;

  Node next;  

  public Node(String value){

    this(value, null);

  }

  public Node(String value, Node next){

    this.value = value;

    this.next  = next;

  }  

}

Let us test our code by establishing the connectivity between nodes

public static void main(String [] args){

    Node n1 = new Node("A");

    Node n2 = new Node("B");

    Node n3 = new Node("C");

    Node n4 = new Node("D");

    Node n5 = new Node("E");

Let us create a connection between nodes to generate 

    n2.next = n1;

    n1.next = n3;

    n3.next = n5;

    n5.next = n4;

    n4.next = null;

By attempting to print:

System.out.println(n2);

What are we expected to get?

Node@7d2d3583

Since we are dealing with objects, we need to extract the actual value that holds the Node object. In this case, will be:

System.out.println(n2.value);

Will print the value of “B”. How about the next value, i.e., the “A”?

System.out.println(n2.next.value); 

If we plan to print the entire list we should do something like:

System.out.println(n2.value);                     //prints B

System.out.println(n2.next.value); //prints A

System.out.println(n2.next.next.value);           //prints C

System.out.println(n2.next.next.next.value);      //prints E

System.out.println(n2.next.next.next.next.value); //prints D

How can we avoid repetition?

Obviously, we need to avoid the redundancy of the .next.next…. The question is how? There are different ways to do it

Approach 1: Use the initial node to navigate through the connectivity  

while(n2 != null){

      System.out.println(n2.value);

      n2 = n2.next;

}

The previous routine indeed prints the elements of the connectivity. However, if we attempt to do this again, we will not succeed, since n2 will already be null. 

Approach 2: Use a “dummy” to copy the reference of the initial point  

Node dummy = n2;

while(dummy != null){

      System.out.println(dummy.value);

      dummy = dummy.next;

}

Approach 3: Define a toString() in the class Node 

The class Node has a field (next), which its type is Node. This is the recursive concept that even defining a class it owns a connection to itself through the next field. 

public String toString(){

    return value+"->"+next;

}

Related Videos

Useful Files