Creating a circular linked list

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

32 Replies - 7507 Views - Last Post: 04 October 2011 - 08:38 PM Rate Topic: -----

#16 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 03 October 2011 - 07:19 PM

pbl, thanks for you reply. I would like to clarify that I am allowed to use front and end markers but I am not allowed to create
dummy head and tail nodes. That is, head and tail with null values.
With due respect to what you suggested, I have used the beginMarker node in my addFront method. Does that method make sense?
Here's what I have done:


public class GenLinkedList<AnyType> 
{ 
          private int theSize; 
	  private Node<anyType> beginMarker; 
	  private Node<AnyType> endMarker; 


   public static class Node<AnyType> 
   {
   
       public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) 
	  { 
	        data = d; 
		previous = p; 
		next = n; 
	  } 
	  
	  AnyType next; 
	  Node<AnyType> previous; 
	  Node<AnyType> next; 
    } 
	
      public void addFront(AnyType d) 
	{ 
      // if size is zero, then create a new node with a data 
      // this new node doesnt have a next or previous node,
      // so both are null
	  if(theSize ==0) 
	  
	  beginmarker = new Node<AnyType>  (d,null,null); 
	  
         // else, create a node with a data, with null previous link, and a link to the next node. 
	  else
	   
	     beginMarker = new Node<AnyType>(d,null,beginMarker.next); 
    } 



pbl, I am more than open to follow your suggestion if this turns out to be wrong.However, I would appreciate if you can give an example to what you explained because I am confused by ur explanation.
Was This Post Helpful? 0
  • +
  • -

#17 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Creating a circular linked list

Posted 03 October 2011 - 07:22 PM

beginMarker = new Node<AnyType>(d,null,beginMarker.next);

No if your node is [b]circular[/b[ as its name says, the backward pointer of the head is the last node.

You do not need two "markers" for a circular linked list
What will be use of it ?
The lastNode is always the headerMarker backward pointer

This post has been edited by pbl: 03 October 2011 - 07:24 PM

Was This Post Helpful? 0
  • +
  • -

#18 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 03 October 2011 - 07:25 PM

what if I want to create a method called removeLast..will it be easy to do it with single node ?
Was This Post Helpful? 0
  • +
  • -

#19 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Creating a circular linked list

Posted 03 October 2011 - 07:30 PM

View Postimu_1, on 03 October 2011 - 10:25 PM, said:

what if I want to create a method called removeLast..will it be easy to do it with single node ?

The last node is the node pointed by the header backward pointer so the process is
- get last node (using header backward bointer)
- get the one before the last node using the last node backward pointer
- have the header backard pointer to point to the one before last node (this node becomes by this operation the last node)
- have that new last node forward pointer to point to the header

the old last node becomes an orphan (is removed) because
the header backward pointer does not point to it anymore
the ex one before last forward pointer points now to the head node
Was This Post Helpful? 0
  • +
  • -

#20 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 03 October 2011 - 07:50 PM

ok, thanks. I understood your explanation on remove.So, as far my addBefore method is concerned,lets say I the beginMarker is the uniqueMarker, then,is my addBefore method correct ?
Was This Post Helpful? 0
  • +
  • -

#21 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Creating a circular linked list

Posted 03 October 2011 - 09:01 PM

/*
 *  Node-1 is the master.
 *  
 *     Node-1             Node-2             Node-3
 *     forward-> node-2   forward-> node-3   forward-> Node-1 
 *     backward> node-3   backward-> node-1  backward-> Node-2
 *     
 *     adding node-0 you want
 *     
 *     Node-0             Node-1             Node-2             Node-3
 *     forward-> node-1   forward-> node-2   forward-> node-3   forward-> node-0
 *     backward> node-3   backward-> node-0  backward-> node-1  backward-> node-2
 *     
 *     So to insert at the beginning
 *     
 *     -The last node Node-3 (which is the backward pointer of the master node) forward 
 *      pointer should now point to the new node
 *     - Node-1 (old master) backward pointer should point to the new node
 *     - New node becomes the master:
 *       its forward pointer points to the old master Node-1
 *       its backward pointer should point to the last node (used to be the backward pointer of the old master)
 */


macosxnerd101 wrote a tutorial

http://www.dreaminco...-list-tutorial/
Was This Post Helpful? 2
  • +
  • -

#22 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 04 October 2011 - 04:51 AM

pbl,thanx for the reply.I understood you rexplanation. I just wanna make one ask this, that when I add my first node in the list,then will the backward link of my node point to the node itself or will it start to exist whenver there are two or more nodes ?
Was This Post Helpful? 0
  • +
  • -

#23 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 04 October 2011 - 09:54 AM

Any ideas?
Was This Post Helpful? -2
  • +
  • -

#24 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10658
  • View blog
  • Posts: 39,573
  • Joined: 27-December 08

Re: Creating a circular linked list

Posted 04 October 2011 - 09:56 AM

Yes- current.previous = current when adding the first Node. Also, please avoid bumping your thread every few hours. We are all volunteers here and we all see your thread.
Was This Post Helpful? 1
  • +
  • -

#25 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 04 October 2011 - 11:16 AM

Based on the inputs I got from all of you, I have started to write the method addFront().

Here's the what I have come up with:

       public class GenericLinkedList<AnyType> 
{ 
    private int theSize; 
	  private Node<AnyType> beginMarker; 
   
   
   public static class Node<AnyType> 
   {
   
      public Node(AnyType d) 
	  { 
	     d = data; 
	  } 
	  
      public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) 
	  { 
	    d = data; 
		p = previous ;
		n = next ;
	  } 
	  
	  AnyType data; 
	  Node<AnyType> previous; 
	  Node<AnyType> next; 
    } 
	
	public void addFront(AnyType d) 
	{ 
	  if(theSize ==0) 
	  {
	     Node<AnyType> newNode = new Node<AnyType>(d); 
		 newNode.next = newNode; 
		 newNode.previous = newNode; 
		 beginMarker = newNode; 
		 theSize = 1;
	    System.out.println("If part touched");
	  }   
	  else
	  {
	     System.out.println("Else part");
	     Node<AnyType> newNode = new Node<AnyType>(d);
         
		 beginMarker.previous = newNode; 
		 beginMarker.next = newNode; 
	     newNode.next = beginMarker; 
		// beginMarker =  newNode; 
		 theSize++; 
	  } 
	} 

	public int getSize() 
	{ 
	   return theSize; 
	} 
	
	 
	public static void main(String [] args) 
	{ 
	   GenericLinkedList<Integer> list = new GenLinkedList<Integer>(); 
	   
	   list.addFront(7); 
	  // list.addFront(8);
	   System.out.println("The size of the node is" + list.getSize()); 
	   System.out.println("The beginMarker " + list.beginMarker.data); 
	} 
} 



The issue here is that beginMArker.data gives me null. I am not sure why.. I would appreciate if I can get some guidance on this.
Thanks.
Was This Post Helpful? 0
  • +
  • -

#26 Fuzzyness  Icon User is offline

  • Comp Sci Student
  • member icon

Reputation: 669
  • View blog
  • Posts: 2,438
  • Joined: 06-March 09

Re: Creating a circular linked list

Posted 04 October 2011 - 11:25 AM

You never instaniate it.
Instantiated: Node<AnyType> newNode = new Node<AnyType>(d)
Not Instantiated: private Node<AnyType> beginMarker;
Was This Post Helpful? 0
  • +
  • -

#27 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 04 October 2011 - 11:49 AM

But in my addFront method ,I am setting the beginMarker to be equal to newNode.
Was This Post Helpful? 0
  • +
  • -

#28 Fuzzyness  Icon User is offline

  • Comp Sci Student
  • member icon

Reputation: 669
  • View blog
  • Posts: 2,438
  • Joined: 06-March 09

Re: Creating a circular linked list

Posted 04 October 2011 - 11:53 AM

Yes, you assign it a variable... but you never instantiate it like I said before.. What is the difference in those 2 statements I posted before? You are forgetting to instantiate it. As in = new Node(params);
Was This Post Helpful? 0
  • +
  • -

#29 imu_1  Icon User is offline

  • D.I.C Regular

Reputation: -6
  • View blog
  • Posts: 256
  • Joined: 03-June 11

Re: Creating a circular linked list

Posted 04 October 2011 - 12:07 PM

If I instantiate the beginMarker, then I will create a dummy node. This would violate the assignment instructions.

So, I was wanting to assign beginMarker to the first node (when size is zero). In this way, I can get away with creating a dummy node. But then the instantiation issue arises. I am still unable to figure out how I can code it in a way that it doesnt involve the use of dummy head and tail node.
Was This Post Helpful? 0
  • +
  • -

#30 Fuzzyness  Icon User is offline

  • Comp Sci Student
  • member icon

Reputation: 669
  • View blog
  • Posts: 2,438
  • Joined: 06-March 09

Re: Creating a circular linked list

Posted 04 October 2011 - 12:13 PM

if(theSize ==0)
      {
         Node<AnyType> newNode = new Node<AnyType>(d);
         newNode.next = newNode;
         newNode.previous = newNode;
         beginMarker = newNode;
         theSize = 1;
        System.out.println("If part touched");
      } 

So this newNode is Scoped.. so once the if statement end it will go away.. So why not just make it..
beginMarker = new Node<AnyType>(d);
Then do whatever else you need to. It creates an instantiation, you don't use a dummy. Haven't worked too much in Nodes but it made sense to me..
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3