Results 1 to 11 of 11
  1. #1
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Implementing a tree using a Linked List.

    Hey so I have to implement a binary tree using a linked list and I'm stuck... 1) We have to use the position ADT and I don't get too much how that works... I implemented my own interface Position as follow:

    Java Code:
    public interface Position {
    	Object element();
    }
    However, what does position do exactly? Is it like an actual position in a line ( i.e: first, second) and how does Java read it when ran ( its hard to formulate this as I never seen it worked. So I can't visualize what is happening).

    Secondly, my Linked List has an inner Node class which implements Position. However, I don't know how to create the tree from it. Here's the code ( it is a bit long sorry)
    Java Code:
    public class LinkList<E>  {
    
    	private class Node<T> implements Position{
    		private Node<T> previous;
    		private Node<T> next;
    		private T data;
    		public Node(Node<T> prev, T data, Node<T> next){
    			previous = prev;
    			this.data = data;
    			this.next = next;
    		}
    		public T element() {
    			return data;
    		}
    		public void setData(T Data){
    			this.data = data;
    		}
    		
    		public Node<T> getNext(){
    			return next;
    		}
    		public Node<T> getPrev(){
    			return previous;
    		}
    		public void setNext(Node<T> e){
    			next = e;
    		}
    		public void setPrev(Node<T> e){
    			previous = e;
    		}
    		
    	}
    	  private Node<E> first;
    	  private Node<E> last;
    	  private int size;
    	public LinkList(){
    		first = null;
    		last = null;
    		size = 0;
    	}
    	public LinkList(Node<E> f, Node<E> l, int s){
    		first = f;
    		last = l;
    		size = s;
    	}
    	public int getSize(){
    	 return size;	
    	}
    	public boolean isEmpty(){
    		if(size==0)
    			return true;
    		else
    			return false;
    	}
    	public Position first()
        {
            return first;
        }
    
        public Position last()
        {
            return last;
        }
        public E getElem(){
        	
        }
        public Position before(Position p) throws Exception
        {
            Node<E> n = (Node) p;
            try{
                return n.getPrev();
            }catch(NullPointerException ex)
            {
                System.out.println("Position Doesn't Exists");
            }
        }
    
        public Position after(Position p) throws Exception
        {
            Node<E> n = (Node) p;
            try{
                return n.getNext();
            }catch(NullPointerException ex)
            {
                throw new Exception("Position Doesn't Exists");
            }
        }
    
    // Update methods
    
        public void insertFirst(Object data)
        {
            Node<E> node;
            if(isEmpty())
            {
                Node<E> prev = null;
                Node<E> next = null;
                node  = new Node(prev,data,next);
                first = node;
                last = node;
            }
            else
            {
                Node<E> prev = null;
                Node<E> ext = first;
                node  = new Node(prev,data,next);
                first.setPrev(node);
                first = node;
            }
            size++;
        }
    
        public void insertLast(Object data)
        {
            Node<E> node;
            if(isEmpty())
            {
                Node<E> prev = null;
                Node<E> next = null;
                node  = new Node(prev,data,next);
                first = node;
                last = node;
            }
            else
            {
                Node<E> prev = last;
                Node<E> next = null;
                node  = new Node(prev,data,next);
                last.setNext(node);
                last = node;
            }
            size++;
        }
    
        public void insertBefore(Position p, Object data) throws Exception
        {
            Node<E> cur = (Node) p;
            Node<E> prev;
            try{
                prev = cur.getPrev();
            }catch(NullPointerException ex)
            {
                throw new Exception("Position Doesn't Exists");
            }
            Node<E> next = cur;
            Node<E> node;
            node  = new Node(prev,data,next);
            next.setPrev(node);
            if(cur!=first)
                prev.setNext(node);
            else
                first=node;
            size++;
        }
    
        public void insertAfter(Position p, Object data) throws Exception
        {
            Node<E> cur = (Node) p;
            Node<E> prev = cur;
            Node<E> next;
            try{
                next = cur.getNext();
            }catch(NullPointerException ex)
            {
                throw new Exception("Position Doesn't Exists");
            }
            Node<E> node;
            node  = new Node(prev,data,next);
            prev.setNext(node);
            if(cur!=last)
                next.setPrev(node);
            else
                last=node;
            size++;
        }
    
        public Object remove(Position p) throws Exception
        {
            Node<E> n = (Node) p;
    
            Object data = n.element();
            if(isEmpty())
            {
                throw new Exception("List is Empty");
            }
            else
            {
                Node<E> prev,next;
                if(n==first && n==last)
                {
                    first = null;
                    last = null;
                }
                else if(n==first)
                {
                    prev = null;
                    next = n.getNext();
                    next.setPrev(prev);
                    first = next;
                }
                else if(n==last)
                {
                    prev = n.getPrev();
                    next = null;
                    prev.setNext(next);
                    last = prev;
                }
                else
                {
                    prev = n.getPrev();
                    next = n.getNext();
                    prev.setNext(next);
                    next.setPrev(prev);             
                }   
                size--;
            }
            return data;
        }
    
    	
    }
    Then I have to create a tree with the following methods (I'll just give a few as I don't want to go through it all on here):
    getElement( ): returns the element stored at this position
    root(p): returns the position of the root of the tree
    parent( ): returns the position of the parent of position p (or null if p is the root)
    children(p): returns an iterable collection containing the children of position p.

    Now, in my tree, the getElement() seems kinda hard because I have to access it using the position and THEN access the data inside my node ( which is private and only accessible by linkedlist). My question is, am I even doing this right or did I skip something? If I am doing this right, how on earth can I access the Element using the position. It just all seems so.... counterintuitive.

    Sorry for the long post guys!

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Implementing a tree using a Linked List.

    Quote Originally Posted by Manddd View Post
    Now, in my tree, the getElement() seems kinda hard because I have to access it using the position and THEN access the data inside my node ( which is private and only accessible by linkedlist). My question is, am I even doing this right or did I skip something? If I am doing this right, how on earth can I access the Element using the position. It just all seems so.... counterintuitive.
    Your List implementation should have a getElement() method. Your linked list implementation is simply the data model (the way the information is stored). So when
    you invoke the getElement() method to get an element, it then calls the linked list's equivalent method to get the appropriate element and return it. Your list implementation need not know any details about the model. All internal values of the model (left node, right node, etc) which are not part of the linked list public interface may be private.

    Here is a small example:

    Java Code:
    class List<E> {
        LinkedList<E> linkedList= new LinkedList<>();
        public E getElement(int index) {
            return linkedList.getElement(index);
        }
        // other useful methods go here
    }
    
    class LinkedList<E> {
         private Node left;
         private Node right;
         // etc.
        public E getElement(int index) {
           // retrieval logic goes here
        }
        //your  other methods and data
        // go here
    }
    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Re: Implementing a tree using a Linked List.

    Sorry, this might be a redundant question but you created another separate class to use linkedlist? It seems to be you could do it this way:

    Create node class inside Linked List --> Implement Linked list method to reach node class --> Create tree that take a linked list. I.e : Instantiate node 1 that will hold a pointer to node 2 and 3 where 2 will hold to n+2 and n+3 and so on and so forth. I don't know if this is right, I've never done the actual implementation of a tree, and even less with a position

  4. #4
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Implementing a tree using a Linked List.

    Quote Originally Posted by Manddd View Post
    Sorry, this might be a redundant question but you created another separate class to use linkedlist? It seems to be you could do it this way:

    Create node class inside Linked List --> Implement Linked list method to reach node class --> Create tree that take a linked list. I.e : Instantiate node 1 that will hold a pointer to node 2 and 3 where 2 will hold to n+2 and n+3 and so on and so forth. I don't know if this is right, I've never done the actual implementation of a tree, and even less with a position
    You could do it certainly do it your way. My suggestion just offers one more level of abstraction. That way, the List class could provide a variety of internal data models (like an array for example). And I am not certain how you would do the index. Since you said a tree in your subject that implies branches rather than just a linear list. So you would need some criteria for tree traversal to get the desired element. Perhaps you just meant regular linked list.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  5. #5
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: Implementing a tree using a Linked List.

    implement a binary tree using a linked list
    I can't see how that would work. Both have nodes that are connected to one or more other nodes, but how can one be used to implement the other?
    If you don't understand my response, don't ignore it, ask a question.

  6. #6
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Re: Implementing a tree using a Linked List.

    Well I am trying to implement a tree. So yes, branches would be what I'm looking for. I thought a linked list is always linear, unless every pointer should point to an array? I.e: Node.next would point to an array and the array would hold the pointer to its 2 children (in this case my tree is binary).

    As for the extra level of abstraction, what do you exactly mean by that? An extra level of manipulation to encapsulate the data better?

  7. #7
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Implementing a tree using a Linked List.

    Quote Originally Posted by Manddd View Post
    I thought a linked list is always linear, unless every pointer should point to an array?
    A linked list is linear. A node points to the next node which points to the next node and so on. But a binary tree can be made up of a number of linked lists. You have a node which has a left child pointer and a right child pointer. Each child is a node so the process continues as each node has children pointers. In some cases, the nodes also contain pointers to the parent. In Java, those pointers are simply references to node objects. But basically you are using linked lists to construct the tree.

    As for the extra level of abstraction, what do you exactly mean by that? An extra level of manipulation to encapsulate the data better?
    Yes! But basically it separates the model (how you store the data) from the implementation (how you access the data).


    And as I said before, trying to get item #234 from a tree is not as simple as getting it from an array or linked list (not a tree). for the latter two you either index it directly or count the nodes (other optimizations may also apply).

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  8. #8
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Re: Implementing a tree using a Linked List.

    Quote Originally Posted by Norm View Post
    I can't see how that would work. Both have nodes that are connected to one or more other nodes, but how can one be used to implement the other?
    I believe a tree is just the way the linked list is done... I can't really say as I don't understand myself and my teacher seems to be ... useless with this. however I can show a picture of what were asked to do:



    sorry for the size... ugh

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: Implementing a tree using a Linked List.

    Ok. The project is to build a tree using links (is there any other way?), not using linked lists. Each node has links to the other nodes it should be connected to.
    If you don't understand my response, don't ignore it, ask a question.

  10. #10
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Re: Implementing a tree using a Linked List.

    So, that means I misunderstood the whole concepts. My apologies for not explaining this the right way. So, when creating a link class, I would make it so everytime I insert a node it would be to the left, than to the right? I.e: Insert nodeAfter (p,e) would insert e after p (so let's say p+1 if left child and p+2 if right child). I wouldn't have anything that would use linklist method that would check for last and first right? Just for a root?

    Also, what is confusing is I thought implementation is solely done through Arrays, ArrayList OR LinkedList

  11. #11
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: Implementing a tree using a Linked List.

    when creating a link class,
    There wouldn't be a Link class. A link is a variable in a node that holds the address (links to) another node in the structure.

    I'm not sure what you mean by "p+1" and "p+2"

    implementation is solely done through Arrays, ArrayList OR LinkedList
    A structure like a tree or a linked list can be built using an array or ArrayList that holds nodes. The links between nodes would be their index into the array.
    Say a node at slot 5 in an array "links" to a node in slot 22, then the nextNode pointer's value in the node at slot 5 would be 22, the location of the next node.

    I don't see how a LinkedList would be used.
    If you don't understand my response, don't ignore it, ask a question.

Similar Threads

  1. Implementing Singly Linked List
    By Robben in forum New To Java
    Replies: 21
    Last Post: 04-20-2015, 01:55 AM
  2. Linked list and binary tree
    By urielik in forum Advanced Java
    Replies: 1
    Last Post: 12-22-2011, 02:49 PM
  3. Linked list and binary tree
    By urielik in forum New To Java
    Replies: 1
    Last Post: 12-22-2011, 12:40 PM
  4. Replies: 8
    Last Post: 10-17-2011, 09:17 AM
  5. Implementing a singly linked list
    By Onra in forum New To Java
    Replies: 2
    Last Post: 04-12-2010, 09:19 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •