Doubly Linked List with (array of?) Singly Linked Lists

[dogface13]

Hi Daniweb community,

I have implemented a node class, DoublyLinkedList class and a SinglyLinkedList class.

For each DoublyLinkedList node created, there is supposed to be a reference to a NEW SinglyLinkedList. Meaning each DLL Node has its own SLL. I have such a reference created which is a single node where I even put into the SLL. The problem being is that every time I add something to the SLL, the reference node gets every single piece of data (and I am only creating one SLL for the entire thing).

Also the number of nodes aren't fixed as they are added over time. I have an idea, which would be indexing each DLL node and creating a SLL to each of them, but was wondering if this community has any more efficient or better ideas.

For example,

        dlist.create("A", "hyphen"); //creates a doubly linked node with A as a letter index and hyphen as data
        dlist.insert("A", "he-man"); //insert a singly linked node with A as a letter index and he-man as data
        dlist.insert("A", "koolaid");
        dlist.insert("A", "shortkid");
        dlist.create("C", "subtitle");
        dlist.insert("C", "gintaman");

Should yield in the linked lists:

A(hyphen) ->A(he-man)->A(koolaid)->A(shortkid)
^
|
v
C(subtitle) ->C(gintaman)

Right now, my DLL and SLL are good SEPARATELY. I haven't the slightest clue how to actually have the doubly linked list reference the singly.

[somjit{}]

Okay , so for life on the heap , what i guess this means is that Your DLL is a datastructure that hold elements of type SLL ?

Perhaps that makes it easier to understand whats going on and how things can be improved ..

[dogface13]

Sorry if it is confusing to read. I have two different data structures. One Doubly and one singly linked list.

The singly cannot exist without the doubly.

The doubly is first created, and at the start holds a reference to a singly linked list. As nodes are being inserted into the singlyLinkedList with the same index as the doubly, the SLL starts to populate.

I hope this diagram kind of shows a little bit of what is supposed to be going on.

DLL  
 _     _ _
|_|-> |_|_|  SLL
|_|    _ _
|_|-> |_|_|  SLL
|_|
|_|

[somjit{}]

The singly cannot exist without the doubly.

In java terms , that can be said as singly being an inner class of doubly.
But your diagram to me all the more strenthens the idea that DLL is a memory space that holds objects of type SLL. And i dont see anything wrong with that. (Except for cases where data is big and memory as well as execution time are important design factors)

[dogface13]

Well, the doubly has its own data as well and I am having trouble having the DLL hold a reference to SLL.

I have both of the data structures implemented, just can't seem to figure out how to...make the DLL hold the SLL.

Like, I'm creating SLL whenever the letter index is the same, but it seems that I am only creating only one SLL with only one node..and even though my SLL add method works, it doesn't seem to work when I am using it in my DLL class. Also, the one node seems to be holding all of the data. So I am wondering what other options I can use because I can't think of any.

[somjit{}]

DLL<SLL> mydll = new DLL<SLL>()

If you have some expirience with generics , try making DLL take in generic type , and then above line will work. Maybe post your code here full so we can see whats going on ?

[dogface13]

DLL Class

Group and groupName is the index letter of the lists and I have three adding methods. One to add elements to the DLL, one to add SLL elements which is supposed to call the add method in the SLL.

import java.util.NoSuchElementException;


public class DoublyLinkedList<E>
{// doubly linked list class
    private Node head = new Node(null,null);    // node for the head of a list
    private Node tail = new Node(null,null);    // node for the end of a list
    private Node SLLNode = new Node(null,null); 
    private int count = 0;                        // number of nodes in a list
   // private SinglyLinkedList<String> sll = new SinglyLinkedList<String>();
    SinglyLinkedList<E> sll = new SinglyLinkedList<>();


    public DoublyLinkedList()
    {// initialize list
        head.setPrev(null);
        head.setNext(tail);        // head points to tail
        tail.setPrev(head);        // tail points to head
        tail.setNext(null);
        head.setSinglyLink(SLLNode);
        tail.setSinglyLink(SLLNode);
    }// initialize list
    public void create(String letter, String data) throws IndexOutOfBoundsException
    {// add node at index with data
        Node temp = new Node(letter, data);// create a node containing data

        if(count == 0)
        {
            head = temp;
        }
        else if(count == 1)
        {
            head.setNext(temp);
            temp.setPrev(head);
            tail = temp;
        }
        else
        {
        Node pointer = head;

        temp.setPrev(pointer);                // and re-adjust linkages in list
        temp.setNext(pointer.getNext());    // to add it at index
        pointer.getNext().setPrev(temp);
        pointer.setNext(temp);
        }
       // sort();
        count++;

    }// add node at index with data


    public void insert(String letter, String data) throws IndexOutOfBoundsException
    {// add node at index with data
        SLLNode = new Node(letter,data);
        Node temp = head;


         SinglyLinkedList<E> indexing = new SinglyLinkedList<>();
        boolean letterFound = false;
          while(temp != null)
          {
              //System.out.println("hihi");
              if(temp.getGroupName().equals(letter))
              {

                  letterFound = true;
                  //if the sll is empty, set a link to the newNode and place it inside the SLL
                  if(indexing.size()==0)
                  {
                      temp.setSinglyLink(SLLNode);
                      //sll.add(letter, data);
                      indexing.add(letter, data);
                      indexing.sort();
                     // System.out.println(indexing.size());
                  }
                  else
                  {
                     // temp.setSinglyLink(SLLNode);
                      indexing.add(letter, data);
                      indexing.sort();
                      //System.out.println(indexing.size());
                  }
              }
              temp = temp.getNext();
          }
          if(letterFound == false)
          {
              System.out.println("ERROR, NO GROUP FOUND");
          }
          printSList();
    }



    //method to see if the singly linked list is printing properly or not
    public void printSList() {
        Node temp = head;
        //Node n = sll.getHead();
        //System.out.println(n.getData());
        //System.out.println(sll.size());


        while(temp!=null)
        {

            Node n = temp.getSLLNode();
            System.out.println(n.getData());
            System.out.println(n.getGroupName());
        //  System.out.println(n);
            //while(n != null)
            {

            //  System.out.println(n.getData());
                //System.out.println("asdasd");
            //  n = n.getNext();
            }
            //System.out.println(n.);
            temp = temp.getNext();
        }
        // TODO Auto-generated method stub

    }
    public String remove(String letter) throws NoSuchElementException
    {

        Node temp = head;
        //temp = temp.getNext();
        if(count == 0)
        {
            return null;
        }
        else if(count == 1)
        {
            return letter;
        }
        else
        {
        while(temp != null)
        {
            if(temp.getGroupName().equals(letter))
            {

                System.out.println("ASDASD");

                Node foundNode = temp;
                Node prevNode = foundNode.getPrev();
                Node nextNode = foundNode.getNext();

                if(foundNode.getPrev() == null)
                {
                    foundNode.setNext(null);
                    nextNode.setPrev(prevNode);
                    head = nextNode;
                }
                else if(foundNode.getNext() == null)
                {
                    foundNode.setPrev(null);
                    prevNode.setNext(nextNode);
                }
                else
                {
                    //dereferences the node that needs to be removed
                    foundNode.setPrev(null);
                    foundNode.setNext(null);

                    //set other references
                    prevNode.setNext(nextNode);
                    nextNode.setPrev(prevNode);
                }
                break;
            }
            temp = temp.getNext();
        }
        }

        count--;
        sort();
        return letter;
    }// remove node at index

    public void setSL(Node sNode)
    {

    }
    public Node getHead()
    {
        return head;
    }

   /* public DoublyLinkedList<E> getDLL()
    {
        //return DoublyLinkedList.this.;

    }*/
    /*public Node getTail()
    {
        return tail;
    }*/

    public int size()
    {// get the current size of list
        return count;
    }// get the current size of list

    public boolean isEmpty()
    {// check if list is empty
     //  SinglyLinkedList.this.
        return count == 0;
    }// check if list is empty



}// doubly linked list class

SLL Class

public class SinglyLinkedList<E> {

    private Node head = new Node(null,null);    // node for the head of a list
    private Node tail = new Node(null,null);    // node for the end of a list
    private int count = 0;    // number of nodes in a list


    public SinglyLinkedList()
    {
        {// initialize list
            head.setNext(tail);
            tail.setNext(null);
        }// initialize list

    }
    public void add(String letter, String data) throws IndexOutOfBoundsException
    {// add node at index with data
        Node temp = new Node(letter, data); // create a node containing data


        if(count == 0)
        {
            head = temp;
        }
        else
        {
            temp.setNext(head);
            tail = head;
            head = temp;
        }
       // sort();
        count++;

    }// add node at index with data



    public Node getHead()
    {

        return head;
    }

    public String remove(String letter) throws IndexOutOfBoundsException
    {// remove node at index
        Node temp = head;
        //temp = temp.getNext();
        if(count == 0)
        {
            return null;
        }
        else if(count == 1)
        {
            return letter;
        }
        else
        {

            while(temp != null)
            {
                if(temp.getGroupName().equals(letter))     
                {
                    System.out.println("ASDASD");
                    Node foundNode = temp;
                    Node nextNode = foundNode.getNext();
                    Node prevNode = head;
                    while(prevNode != null)
                    {
                        if(prevNode.getNext() == foundNode)
                            break;
                        prevNode = prevNode.getNext();
                    }

                    if (foundNode == head)
                    {
                        foundNode.setNext(null);
                        head = nextNode;
                    }
                    else if (foundNode.getNext() == null)
                    {
                        prevNode.setNext(null);
                    }
                    else
                    {
                        prevNode.setNext(foundNode.getNext());
                        foundNode.setNext(null);
                    }
                    break;
                }
                temp = temp.getNext();

            }
        }
       return letter;
        // index exists
    }// remove node at index*/


    public int size()
    {// get the current size of list
        return count;
    }// get the current size of list



}

Node Class

public class Node
{// node class
    private String data;    // data being stored in a node
    private Node prev;        // pointer to previous node
    private Node next;        // pointer to next node
    private Node sLLNode;       //pointer to singly linked list node
    private String groupName;




    Node(String groupName, String data)
    {// construct node
        this.data = data;
        this.groupName = groupName;
    }// construct node
    Node(String groupName, String data, Node prev, Node next)
    {// construct node with prev/next pointers
        this.groupName = groupName;
        this.data = data;
        setPrev(prev);
        setNext(next);
        setSinglyLink(sLLNode);
    }// construct node with prev/next pointers


    void setSinglyLink(Node node)
    {
        this.sLLNode = node;
    }
    void setPrev(Node prev)
    {// set prev pointer
        this.prev = prev;
    }// set prev pointer
    void setNext(Node next)
    {// set next pointer
        this.next = next;
    }// set next pointer

    Node getPrev()
    {// return where prev is pointing to
        return prev;
    }// return where prev is pointing to
    Node getNext()
    {// return where next is pointing to
        return next;
    }// return where next is pointing to
    Node getSLLNode()
    {// return where next is pointing to
        return sLLNode;
    }// return where next is pointing to
    String getData()
    {// return data in nodea
        return data;
    }// return data in node
    String getGroupName()
    {// return data in nodea
        return groupName;
    }// return data in node
    public void printAll()
     {
         System.out.println(this.data);
        // return ;
     }
}// node class*/

And the tester class

    public class LinkedListTester {

        public static void main(String[] args) throws IOException {
            SinglyLinkedList<String>slist = new SinglyLinkedList<String>();
            DoublyLinkedList<String> dlist = new DoublyLinkedList<String>();  


            dlist.create("A", "hyphen");
            dlist.insert("A", "he-man");
            dlist.insert("A", "shortkid");
            dlist.insert("A", "koolaid");
            dlist.create("C", "subtitle");
            dlist.insert("C", "gintaman");

            Node temp = dlist.getHead();

            while(temp != null)
            {
                System.out.println(temp.getData());
                System.out.println(temp.getGroupName());
                temp = temp.getNext();
            }
}

Basically it is supposed to print in lexicographical order as well, I have a working sort that only works when separate, but it never does that as I believe all the data is being stored in a single node.