linked list

circular doubly linked list

Page 1 of 1

1 Replies - 3126 Views - Last Post: 26 March 2010 - 07:10 PM Rate Topic: -----

#1 Guest_nekopczynski*


Reputation:

linked list

Posted 26 March 2010 - 04:13 PM

I am implementing a circular doubly linked list in java but I dont think I am doing it right. I have a few questions that might clear up some confussion???
1. how do you determine if the list if full if it never ends?
2. right now my code using the data set {1,2,3,4} will display 1,2,3,4,1,2.... so I know that it is kind of working but not there yet?
3. I put a method in the display list function that connects the last element to the first, but I dont think this makes sense. The only time the list is circular is when I print it to the screen. Could someone look at my code and please make a few reccomendations. The names of the files are odd because it is only the first step to a project of implementing a circular DLL.

thankyou for any suggestions

public class Solider{
	
	private Node first; 
	private Node last; 
	
	public Solider(){
		first 					= null; 
		last 					= null;    
	}

	public boolean isEmpty(){
		return first == null;
	}

	public void insert(int n){
		
		Node newNode 			= new Node(n);
		
		if (isEmpty())
			last			 	= newNode;		
		else
			first.previous 		= newNode;
			newNode.next 		= first;
			first 				= newNode;
		
	}	

	public void showList(){
		System.out.print("Soliders:  ");
		Node current = first;
		
		int count=0;
		
		//while (current != null){
		while (count < 9){
			count++;
			
			if (current == last){
				current.next = first;
			}
			 
			current.showNode();
			current = current.next;
		}
		System.out.println("");
	}
	
	
	
	public Node deleteKey(int key){
		Node current 	= first; 
		
		while (current.info != key){
			current 	= current.next;
			if (current == null) return null;
		}
		if (current == first) first 	= current.next; 
		else current.previous.next 		= current.next;

		if (current == last) last 		= current.previous; 
		else current.next.previous 		= current.previous;
		
		return current;
	}
	
	

	
	
	
	public static void main(String[] args){
		Solider josephus = new Solider();

		josephus.insert(1);
		josephus.insert(2);
		josephus.insert(3);
		josephus.insert(4);

		
		josephus.showList();


		josephus.deleteKey(1);
		josephus.deleteKey(2);
		josephus.deleteKey(3);
		josephus.deleteKey(4);
		josephus.showList();

		
	}

}

class Node {
  public int info; 
  public Node next; 
  public Node previous; 

  public Node(int n) {
    info = n;
  }

  public void showNode(){
    System.out.print(info + " ");
  }

}



Admin Edit: [/b]Please[/b] use code tags when posting your code. Code tags are used like so => :code:

Thanks,
PsychoCoder :)

Is This A Good Question/Topic? 0

Replies To: linked list

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10573
  • View blog
  • Posts: 39,147
  • Joined: 27-December 08

Re: linked list

Posted 26 March 2010 - 07:10 PM

Your showList() method shouldn't handle modifying the list structure. Instead you should just iterate through the list. You've got the right idea by using a temp Node here Node current = first;; however, your loop while (count < 9){ is a little off. The only way you'll know when you have iterated through the entire list is when you're back at the head Node. So you may consider using a do-loop, with your condition being current != first. Remember- do loops iterate once before evaluating the condition.

Quote

1. how do you determine if the list if full if it never ends?

Linked Lists (and other dynamic structures) are dynamicall resizable, so I don't understand what you mean by the list being full? Lists are not like arrays, where you want a fixed size. Rather, you want them to have the capacity to grow and shrink as necessary. It is more memory efficient, and allows you more control with the ability to add and remove elements dynamically.

For more information on Linked Lists, you might want to check out my Linked List Tutorial. I cover singly, doubly, and circularly Linked Lists.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1