Results 1 to 16 of 16
  1. #1
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default Linked list and quadTree

    hello, would you please provide me with simplified or even advanced algorithms for doubly linked-list and Quad-Tree??

    i attempted the linked-list but unfortunately even the start was abit confusing to me.

    Kind Regards,

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Quote Originally Posted by amrmb09 View Post
    hello, would you please provide me with simplified or even advanced algorithms for doubly linked-list and Quad-Tree??


    What do you mean "provide me with algorithms"? In what form? In Java code?

  3. #3
    j2me64's Avatar
    j2me64 is offline Senior Member
    Join Date
    Sep 2009
    Location
    Zurich, Switzerland
    Posts
    962
    Rep Power
    5

    Default

    Quote Originally Posted by amrmb09 View Post
    hello, would you please provide me with simplified or even advanced algorithms for doubly linked-list and Quad-Tree??

    i attempted the linked-list but unfortunately even the start was abit confusing to me.

    Kind Regards,

    was is confusing you? this forum is for answering such questions and not providing code out-of-the-box.

  4. #4
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    Quote Originally Posted by j2me64 View Post
    was is confusing you? this forum is for answering such questions and not providing code out-of-the-box.
    hello, i'm afraid that i have not clarified my point.
    i havnt asked for providing ajave code, no just how the linked list works, only the principle not the code. because i want to implement it.
    that's all
    sorry for inconvenience

  5. #5
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    Quote Originally Posted by Fubarable View Post
    What do you mean "provide me with algorithms"? In what form? In Java code?
    hello, i'm afraid that i have not clarified my point.
    i havnt asked for providing ajave code, no just how the linked list works, only the principle not the code. because i want to implement it.
    that's all
    sorry for inconvenience

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by amrmb09 View Post
    hello, i'm afraid that i have not clarified my point.
    i havnt asked for providing ajave code, no just how the linked list works, only the principle not the code. because i want to implement it.
    that's all
    sorry for inconvenience
    You don't have to implement doubly linked lists because it has already been done for you; the LinkedList class is part of the Collection framework and implements doubly linked lists. If you have trouble implementing it don't even start to think about quad-trees because that data structure is far more complex than a simple doubly linked list.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    You don't have to implement doubly linked lists because it has already been done for you; the LinkedList class is part of the Collection framework and implements doubly linked lists. If you have trouble implementing it don't even start to think about quad-trees because that data structure is far more complex than a simple doubly linked list.

    kind regards,

    Jos
    thank you for replying.
    i know that linked list is internally implemented in java, but i want to practice it
    as well as queues,stacks and trees just for practicing for my self except you have better recommendation to improve my programming skills, i would be happy to hear.

  8. #8
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    now, when i excute the following code, i receve the following compilation errors

    Exception in thread "main" java.lang.NullPointerException
    at Node.createNode(Node.java:28)
    at LinkedList.main(LinkedList.java:6)

    Java Code:
    public class Node
    {
        String data;
    	Node prev;
    	Node next;
    	int index;	
    		
    		int cnt=0;
    		private Node Header;
    
     public Node()
     {
     	this.data=null;
     	this.prev=null;
     	this.next=null;
     	this.index=getIndex();
     }
     public Node createNode(String x)
     {
     	Node n=new Node();
     	     if(n.index==1)
     	     {
     	     	Header.data=x;
     	     	return Header; //this to distinguish the first node created to be the header and works as reference 
     	     }
     	     else
     	     {
     	     	Header.next=n.prev;
     	     	Header.prev=n.next;
     	     	n.data=x;
     	     	return n; // return new node
     	     }
     }
     
     public int getIndex()
     {
     	return cnt++;
     }
    
    }
    
     main:
    
    [code]
    public class LinkedList
    {
    	public static void main (String[] args)
    	{
    		Node n=new Node();
    		n.createNode("a");
    		System.out.println (n.data);
    		System.out.println (n.cnt);
    		System.out.println (n.getIndex());
    	}
    		
    }
    [/code]

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by amrmb09 View Post
    now, when i excute the following code, i receve the following compilation errors

    Exception in thread "main" java.lang.NullPointerException
    at Node.createNode(Node.java:28)
    at LinkedList.main(LinkedList.java:6)
    A few questions for you to think about: why should every Node have its own Header (that should be 'header' b.t.w.) and why should every Node have its own createNode( ... ) method? Also b.t.w. that 'index' member variable must be a not so well thought out hack; you don't need it.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    thanks,

    concerning:
    1- why every node has its own header?
    no, i implement this code so that only the first not to be a header else, there is no header.

    2-........................................create node?
    to be created or??

    3-why index?
    to get the length of the linkedlist

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by amrmb09 View Post
    1- why every node has its own header?
    no, i implement this code so that only the first not to be a header else, there is no header.
    In your code every node does have its own header (and index value and cnt value); a hackerish solution would be to make header and cnt static but then you can only manage one single list in your code.

    Quote Originally Posted by amrmb09 View Post
    2-........................................create node?
    to be created or??

    3-why index?
    to get the length of the linkedlist
    I don't understand what you're saying at 2); ok, if you want that you can keep track if the length of the list but if you go for the 'static' single list scenario you don't need that index field. I'd say delete what you have now and start from scratch again.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    i havnt asked for providing ajave code, no just how the linked list works, only the principle not the code. because i want to implement it.

    How a doubly linked list works is reasonably straight forward. (I think - I'm no expert about these CSy things).

    As an implementation detail (ie hidden from the user of the linked list) is a Node which contains the "payload" and pointers to the previous and next nodes in the list. And that's it. Its constructor just sets these three elements of its state. It has no behaviour - it no more knows the size of the list than a chocolate in a chocolate box knows how many have been eaten.

    The DoublyLinkedList contains a pointer to the first (or head) node. And the behavour that the list exposes (adding and removing elements, getting the size of the list, finding the index of a given value etc) are all implemented using the nodes.

    Eg: finding the index of a given value. The list will start at the head and keeps jumping to the next node until it finds one whose payload equals the given value. At that point it returns the number of jumps it made.

    Eg: finding the length of the list. The list starts at the head and keeps jumping to the next node until it finds a node that does not have a next. AGain it returns the number of jumps.

    Eg: inserting a given value at a given index. The list starts at the head and follows the next pointers as many times as is required by the given index (a little tricky). It then constructs a new node whose payload is the given value, whose previous pointer is the node it stopped at and whose next node is the next pointer of the node it stopped at. It also looks at the next and previous pointers of the node it has just created and changes the previous and next pointers of those nodes to refer back to that newly created node (if required - because the inserted node may be at the start or end of the list).

    Etc. Where etc means any other behaviour you expect the list to have.

    ------------------------

    It might be worth having a peek at the source of java.util.LinkedList to see how Josh Bloch does it. What you are calling a Node he calls an Item. It's a runty little class with no real behaviour and is not exposed to the user of the linked list.
    Last edited by pbrockway2; 02-13-2011 at 08:23 AM.

  13. #13
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    How a doubly linked list works is reasonably straight forward. (I think - I'm no expert about these CSy things).

    As an implementation detail (ie hidden from the user of the linked list) is a Node which contains the "payload" and pointers to the previous and next nodes in the list. And that's it. Its constructor just sets these three elements of its state. It has no behaviour - it no more knows the size of the list than a chocolate in a chocolate box knows how many have been eaten.

    The DoublyLinkedList contains a pointer to the first (or head) node. And the behavour that the list exposes (adding and removing elements, getting the size of the list, finding the index of a given value etc) are all implemented using the nodes.

    Eg: finding the index of a given value. The list will start at the head and keeps jumping to the next node until it finds one whose payload equals the given value. At that point it returns the number of jumps it made.

    Eg: finding the length of the list. The list starts at the head and keeps jumping to the next node until it finds a node that does not have a next. AGain it returns the number of jumps.

    Eg: inserting a given value at a given index. The list starts at the head and follows the next pointers as many times as is required by the given index (a little tricky). It then constructs a new node whose payload is the given value, whose previous pointer is the node it stopped at and whose next node is the next pointer of the node it stopped at. It also looks at the next and previous pointers of the node it has just created and changes the previous and next pointers of those nodes to refer back to that newly created node (if required - because the inserted node may be at the start or end of the list).

    Etc. Where etc means any other behaviour you expect the list to have.

    ------------------------

    It might be worth having a peek at the source of java.util.LinkedList to see how Josh Bloch does it. What you are calling a Node he calls an Item. It's a runty little class with no real behaviour and is not exposed to the user of the linked list.
    thank you.................

  14. #14
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    In your code every node does have its own header (and index value and cnt value); a hackerish solution would be to make header and cnt static but then you can only manage one single list in your code.



    I don't understand what you're saying at 2); ok, if you want that you can keep track if the length of the list but if you go for the 'static' single list scenario you don't need that index field. I'd say delete what you have now and start from scratch again.

    kind regards,

    Jos
    hi,
    in line 2: i wanted to answer your question which was: why you need for every node create node??
    my answer is: i have create node method to create the node.

    N.B: concerninf the forementioned question i have got my mistake, but i still have few to ask:

    1-what if i want to implement a method that increments when every single node is created??

    2-since i want to implement a doubleLinkedList, how to keep track of the first node to be as a reference, so that, i can link the first node's(header)'s previous link to the last node next link regardless of the length of the linked list??

    3-a side from linked list, what does "this" means: does it refere to the object being created by new??

    4-kindly, if you have any pseudo code concerning the double linked list,please give to me.
    thanx.

  15. #15
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,371
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by amrmb09 View Post
    hi,
    in line 2: i wanted to answer your question which was: why you need for every node create node??
    my answer is: i have create node method to create the node.

    N.B: concerninf the forementioned question i have got my mistake, but i still have few to ask:

    1-what if i want to implement a method that increments when every single node is created??

    2-since i want to implement a doubleLinkedList, how to keep track of the first node to be as a reference, so that, i can link the first node's(header)'s previous link to the last node next link regardless of the length of the linked list??

    3-a side from linked list, what does "this" means: does it refere to the object being created by new??

    4-kindly, if you have any pseudo code concerning the double linked list,please give to me.
    thanx.
    You have to discriminate a single Node in a List and the List itself; the List object can store a reference to the first Node in the List (the 'head' node). Do as Pbrockway2 suggested: open the src.zip file in your JDK directory and read the source code for the LinkedList class; it's a good implementation of a doubly linked list.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  16. #16
    amrmb09 is offline Member
    Join Date
    Nov 2010
    Posts
    75
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    You have to discriminate a single Node in a List and the List itself; the List object can store a reference to the first Node in the List (the 'head' node). Do as Pbrockway2 suggested: open the src.zip file in your JDK directory and read the source code for the LinkedList class; it's a good implementation of a doubly linked list.

    kind regards,

    Jos
    thanks , I will read it

Similar Threads

  1. help with linked list
    By Yakg in forum New To Java
    Replies: 7
    Last Post: 01-24-2011, 06:40 PM
  2. Linked list inside a linked list
    By viperlasson in forum New To Java
    Replies: 5
    Last Post: 07-26-2010, 11:15 PM
  3. Linked List
    By basma in forum JCreator
    Replies: 0
    Last Post: 02-03-2010, 08:34 AM
  4. Linked List integer list
    By igniteflow in forum Advanced Java
    Replies: 1
    Last Post: 12-10-2008, 08:53 PM
  5. Linked List
    By rnavarro9 in forum New To Java
    Replies: 0
    Last Post: 11-29-2007, 03:42 AM

Posting Permissions

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