Why to have a parent class for linked list

user_5737572 0
Viewed 676

This is a general question, maybe about OOP concept. I am just starting with DS implementation in JAVA. I am trying to implement Linked List and on all online rsources, I see a similar practice:

  1. Make a node class.
  2. Make a class Linked List that has a node object.

Similarly I saw for stack, queues and trees. My question is, if I implement LinkedList by only having one class that looks like below:

 class LinkList {
     int data;
     LinkList next; }

I am still able to do all the operations. So the concept of having a second class that contains a root or a header is only for OOP purpose or something else? I wrote the following code and it works all well without the need to have a header pointer. I use a references variable in all the methods and the main class's object still keeps the track of the head.

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class LinkList {
    int data;
    LinkList next;

    LinkList(){
        data = 0;
        next = null;
    }

    LinkList(int data) {
        this.data = data;
        next = null;
    }
    LinkList insertAtBegin(int data){
        LinkList newBegin = new LinkList(data);
        newBegin.next = this;
        return newBegin;
    }
    void insertAtPlace(int data, int insertData){
        LinkList newNode = new LinkList(insertData);
        LinkList iterator = this;
        while(iterator!=null && iterator.data!=data){
            iterator = iterator.next;
        }
        if(iterator.data == data)
        {
            newNode.next = iterator.next;
            iterator.next = newNode;
        }
    }
    void insertAtLast(int data) {
        if(next == null){
            next = new LinkList(data);
        }
        else{
            next.insertAtLast(data);
        }
    }

}

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        LinkList linkList = new LinkList(6);
        linkList.insertAtLast(5);
        linkList.insertAtLast(3);
        linkList.insertAtLast(2);
        linkList.insertAtLast(1);

        linkList = linkList.insertAtBegin(10);
        LinkList iterator = linkList;
        while(iterator!=null){
            System.out.print(iterator.data);
            iterator = iterator.next;
        }
        System.out.print("\n");
        linkList.insertAtPlace(5,-1);
        iterator = linkList;
        while(iterator!=null){
            System.out.print(iterator.data);
            iterator = iterator.next;
        }
    }
}
data-structures linked-list java
3 Answers

You must keep track of the head of the linked list somewhere. Otherwise, how would you iterate over the entire list, or search for an element in the list?

If your LinkList is essentially a node (with data and reference to the next node), you would have to implement all the linked list operations (add, delete, etc...) in some separate class that keeps track of the head node of the list.

This brings you back to a linked list class that uses a node class.

As for the code you added, LinkList insertAtBegin(int data) will only insert a node at the beginning of the list if you call it on the first node of the list. But there's nothing stopping you from calling it on any node of the list, in which case it will essentially return a new list that starts with the new elements and ends with a sub-list of the original list.

user_12215710

There are several reasons to have two classes:

  • to distinguish the notion of a list and that of a single node,
  • to avoid the awkward returning of the head node from each method,
  • to avoid letting the client of the class have the responsibility to keep track of the head node,
  • to hide the implementation details, so that the class could be more easily replaced with an equivalent one,
  • etc...
user_70364190

Your LinkList class would just be a node class in the first example, because it holds the data and the node that comes after it

The general purpose of having a LinkedList class is to have a "wrapper" for the list, it's just a class that holds the head of the list (which in the case of a linked list, is the list) and perhaps some functionalities such as a find function or anything else you'd need.

so in your case (2nd example) it is just a wrapper class that implements some extra functionalities (insertAtBegin(), insertAtPlace() and insertAtLast())

user_103379160
Related