Results 1 to 11 of 11
 11052015, 11:17 PM #1Member
 Join Date
 Mar 2015
 Posts
 23
 Rep Power
 0
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(); }
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; } }
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!
 11052015, 11:40 PM #2Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 14
Re: Implementing a tree using a Linked List.
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 }
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 11062015, 01:18 AM #3Member
 Join Date
 Mar 2015
 Posts
 23
 Rep Power
 0
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
 11062015, 01:30 AM #4Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 14
Re: Implementing a tree using a Linked List.
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 11062015, 02:11 AM #5
Re: Implementing a tree using a Linked List.
implement a binary tree using a linked listIf you don't understand my response, don't ignore it, ask a question.
 11062015, 02:14 AM #6Member
 Join Date
 Mar 2015
 Posts
 23
 Rep Power
 0
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?
 11062015, 03:19 AM #7Senior Member
 Join Date
 Jan 2013
 Location
 Northern Virginia, United States
 Posts
 6,226
 Rep Power
 14
Re: Implementing a tree using a Linked List.
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?
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 11062015, 05:32 PM #8Member
 Join Date
 Mar 2015
 Posts
 23
 Rep Power
 0
Re: Implementing a tree using a Linked List.
 11062015, 05:35 PM #9
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.
 11062015, 05:52 PM #10Member
 Join Date
 Mar 2015
 Posts
 23
 Rep Power
 0
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
 11062015, 08:39 PM #11
Re: Implementing a tree using a Linked List.
when creating a link class,
I'm not sure what you mean by "p+1" and "p+2"
implementation is solely done through Arrays, ArrayList OR LinkedList
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

Implementing Singly Linked List
By Robben in forum New To JavaReplies: 21Last Post: 04202015, 01:55 AM 
Linked list and binary tree
By urielik in forum Advanced JavaReplies: 1Last Post: 12222011, 02:49 PM 
Linked list and binary tree
By urielik in forum New To JavaReplies: 1Last Post: 12222011, 12:40 PM 
Linked list with multiple links to implement Tree data structure
By kavithavr in forum Advanced JavaReplies: 8Last Post: 10172011, 09:17 AM 
Implementing a singly linked list
By Onra in forum New To JavaReplies: 2Last Post: 04122010, 09:19 PM
Bookmarks