Linked list and quadTree

[amrmb09]

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,

[Fubarable]

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?

[j2me64]

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.

[amrmb09]

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

[amrmb09]

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

[JosAH]

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

[amrmb09]

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.

[amrmb09]

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)

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]

[JosAH]

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

[amrmb09]

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

[JosAH]

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.

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

[pbrockway2]

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.

[amrmb09]

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.................

[amrmb09]

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.

[JosAH]

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

[amrmb09]

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