Homework 1

01/20/2014 18:21

 I have spent all weekend trying to figure out what the problem to this assignment is, I've emailed the teacher and not really gotten anywhere. I keep getting null pointer exception. Cannot figure out why. I have a main class that seems to run all the functions without any problem. I will have to start my next assignment earlier in expectation of problems. Since returning null when what was being sought was not possible seemed like the problem, I went through and removed the possibility to return null things intentionally. No difference. I will have to go see my teacher during his office hours.


 

I have now finished the project... quite late but it is done.

The problem ended up being the code that spawned the header node. In my test examples I was not using an empty list so it wasn't a problem since the header's next and previous were being defined after the initialization. But the initial code was header = new header(null, header, header). This turned out not to work because before the line finishes, header is null object, and thus a null pointer. So I had to say header = new header(null, null, null) and then have two lines for header.next = header and header.prev = header.

So I have a doubly linked list implementation of a fireworks program. I have artistically added to it that the fireworks will blink and have a 50% chance of being red, and equal chance of being blue.

I also found that using a doubly linked list, the running time becomes worse a lot more quickly than with an array list. the fps go down at a rate of O(N) and so does the time it takes to render particles. With an Array List, there is no significant difference in these data points with the same parameters.




	
		

			doubly linked list
			max particles
			seconds
			fps
			 
			array list
			max particles
			seconds
			fps
		

		

			 
			726
			14.017682
			30
			 
			 
			726
			12.923905
			30
		

		

			 
			1468
			13.655699
			29
			 
			 
			1503
			12.972476
			30
		

		

			 
			2270
			14.093504
			29
			 
			 
			2260
			12.62602
			30
		

		

			 
			2978
			15.808429
			23
			 
			 
			2976
			13.307398
			30
		

		

			 
			3690
			17.574461
			19
			 
			 
			3692
			13.309422
			30
		

		

			 
			4519
			20.735975
			16
			 
			 
			4451
			13.451353
			30
		

		

			 
			5257
			24.235395
			13
			 
			 
			5196
			12.971419
			30
		

		

			 
			5970
			29.776978
			10
			 
			 
			5957
			13.158617
			30
		

		

			 
			6772
			34.434326
			9
			 
			 
			6701
			13.297068
			30
		

		

			 
			7470
			41.2335
			7
			 
			 
			7443
			12.948578
			30
		

		

			 
			8219
			54.473846
			5
			 
			 
			8098
			13.776996
			28
		

		

			 
			8897
			87.2575
			3
			 
			 
			8915
			13.28593
			29
		

		

			 
			11225
			175.61978
			1
			 
			 
			11129
			13.766596
			30
		

	
	
		
		
		
		
		
		
		
		
	



We are then asked:
Suppose that you have a reference to a node in a singly linked list that is guaranteed not to be the last


node in the list. You do not have references to any other nodes (except by following links). Describe an


O(1) algorithm that logically removes the value stored in such a node from the linked list, maintaining the


integrity of the linked list. (Hint: Involve the next node.)






To solve this, I suggest making the node a pointer to the next node with a single line of code like so:
this = this.next;


The node is a pointer instead of raw data, so by making it a pointer to the next node, the previous node's .next


becomes the node after it, effectively removing the node, which should be cleared by the garbage collector since


it has no more references.




 



	 

      								      		
            					
            

            
            
            					
            

            
            

		
		      
                      
            
  			
            
            
Back