Building Singly LinkedList

Question

I am attempting to build a data structure in Java with inner list that are made up of singly link lists that contain integers. I am having trouble with the architecture of my data structure. It needs to have a inner class with functions that can merge, split, and give the size of the inner lists.

Assume that the size of the inner lists will change and size and data will be removed to consolidate and optimize the data structure.

I have a driver class to interface with the data structure. Then I have a Data structure class which will have the inner class.

Where do I put methods to add/remove top level lists as the singly linked list collapses and expands with my data??

How many classes should I have? A driver, the data structure(with inner class)... more?

I just need a little direction from someone who is a strong coder, I made multiple attempts at top down designs, and I have read and searched. I just need some direction. I attached and image of how the data structure looks.

PLEASE NOTE:

The inner lists must be implemented as a singly-linked lists with dummy headers and tail pointers, and I must not use any data structures from Java Collections API for the inner lists. For the top-level list, I have to use the generic LinkedList class from the Java Collections API.

Answer 1

public class LL {

    class Node
    {
        String data;
        Node next;
        
        Node(String data)
        {
            this.data=data;
            this.next=null;
        }
    }
    

    public  Node head;     
    
    
    public void add_first(String data)
    {
        Node NewNode=new Node(data);
        if(head == null)
        {
            head=NewNode;
            return;
        }
        NewNode.next=head;
        head=NewNode;
    }
    
    public void add_last(String data)
    {
        Node NewNode=new Node(data);
        if(head==null)
        {
            head=NewNode;
            return;
        }
        Node currentNode =head;
        
        while(currentNode.next !=null)
        {
            currentNode=currentNode.next;
        }
        currentNode.next=NewNode;
        
        
        
    }   
    
    
    public void insert_pos(String data,int pos)
    {

        Node NewNode=new Node(data);
        
        Node current=head;
        
        for(int i=0;i<pos-1;i++)
        {

            System.out.println("Current is"+current.data);
            current=current.next;
        }
      
        System.out.println(current.data);
        
        NewNode.next=current.next;
        current.next=NewNode;

        System.out.println("Delete  Element Successfuly at position"+pos);
        
           
        }
    
    
    int counter;
    public void size()
    {
        Node current=head;
        
        
        if(head==null)
        {
            System.out.println("Linked list is Empty.......");
        }
        
        while(current!=null)
        {
            current=current.next;
            counter+=1;
        }
        System.out.println("Linked list size is:"+counter);
        
    }
    public void display()
    {
        Node cur=head;
        
        
        while(cur!=null)
        {

              System.out.print(cur.data+"->");
              cur=cur.next;
        }
        System.out.println("null");
    }
    

    
    public void delete_first()
    {
        Node temp=head;
        head=temp.next;
        System.out.println("Delete First Element Successfuly");
        
    }
    
    
    public void delete_last()
    {
        Node current=head;
        Node lastnode=head.next;
        
        while(lastnode.next!=null)
        {
            current=current.next;
            lastnode=lastnode.next;
        }
        
        current.next=null;      

        System.out.println("Delete last  Element.");
    }
    


    public void delete_pos(int pos)
    {

        
        Node current=head;
        Node last=head.next;
        
        for(int i=0;i<pos-1;i++)
        {

            System.out.println("Current is"+current.data);
            current=current.next;
            last=last.next;
            
        }
      
        
        current.next=last.next; 
        
    }
    


    
    
    
    
 public static void main(String[] args)
 {
     LL list=new LL();
     
     list.add_last("A");
     list.add_last("B");
     list.add_last("C");
     list.add_last("d");
     list.add_last("e");
     
    // list.delete_pos(3);
     //list.delete_first();
     
     //list.delete_last();
     
    // list.insert_pos("nirav",4);
     list.size();

     list.display();
 }

}

  

Answer 2

Note: This looks like a homework, otherwise there would be no need to reinvent the wheel. Knowing this, I won't provide specific code, just pseudocode (except for some keywords like class, int and similar), no useful methods like getters or setters, no additional fields, etc. It will be your job to generate all the necessary Java code to make this work.

---

I don't know where to start, I am new to linked lists

Start by defining the structure of the elements that will go inside the list. How to do this? Review the requirement (emphasys mine):

build a data structure in Java with inner list that are made up of singly link lists that contain integers

You need a data structure that at first can hold an integer value and behaves as singly linked list. From the definition of singly linked list, the structure contains two elements:

1. The integer data to hold
2. The pointer to the next similar data structure.

This can be addressed like this:

class DataStructure {
    int data;
    DataStructure next;
}

Now that you have the structure that supports the singly linked list, you need a new structure that will be the singly linked list and define the behavior of it. This can be addressed as stated in your requirements:

The inner lists must be implemented as a singly-linked lists with dummy header and tail pointers

Moving this into pseudocode:

class SinglyLinkedList {
    DataStructure head;
    DataStructure tail;
}

That's it. Now that you have your SinglyLinkedList, you just need to define the behavior. Again, reviewing the requirements:

It needs to have a inner class with f̶u̶n̶c̶t̶i̶o̶n̶s̶ methods that can merge, split, and give the size of the inner lists.

From here, we can define at least three methods for the SinglyLinkedList data structure: merge, split and size. Adapting the latest class from it:

class SinglyLinkedList {
    DataStructure head;
    DataStructure tail;
    //added this method just to know you need to add data to your singly linked list
    public void add(int data) {
    }
    //you merge a list with another list
    public void merge(SinglyLinkedList singlyLinkedList) {
    }
    //you split the list into two or more lists
    public SinglyLinkedList[] split() {
    }
    //the size of the list is a numeric positive value
    public int size() {
    }
}

EDIT (based on your edit and by looking at the picture)

There's the need to define another data structure that holds a list of singly linked lists. By requirements:

For the top-level list, I have to use the generic LinkedList class from the Java Collections API.

Then, you just need a new structure that uses a LinkedList that will contain your singly linked lists:

class SinglyLinkedListHolder {
    LinkedList<SinglyLinkedList> holder;

    public SinglyLinkedListHolder () {
        holder <- new LinkedList<SinglyLinkedList>();
    }
    //this holder should at least add new singlyLinkedList in the bigger list
    public void add(SinglyLinkedList singlyLinkedList) {
    }
}

---

Note: I notice that you tried to define your structure with generics:

private static class Node<T> {
}

I highly recommend you to not do this until you really grasp the main concepts about how a singly linked list works. It can take some time, but it is better to go step by step. After making this structure to work, then you can easily (in fact, depending on your implementation) replace the structure to:

class DataStructure<T> {
    T data;
    DataStructure next;
}