Results 1 to 10 of 10
  1. #1
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Doubly Linked List. How to add to the head.

    I am working on creating my own Node class and am having trouble adding to the head of a linked list.
    The problem is with the addHead method, which is confusing to me. I make a new node, assign its previous link to null, since it's the head.
    How do I assign its next link to the old head? When I first created the initial node, both its next and previous link are null.


    [ rear ]
    [ data ] New node created with addHead. It's easy to set the rear link to null, but how do I get a reference to the old head node and assign it to the next link?
    [ next ]

    [ rear ]
    [ data ] Initial node. This is assigned as the head and both its links are null.
    [ next ]
    Java Code:
    public class Node<E> {
    	
    	private E data;
    	 
    	private Node<E> next;
    	private Node<E> prev; 
    	
    	
    	
    	//Constructor
    	public Node(E datainit, Node<E> prevLink, Node<E> nextLink)
    	{
    		data=datainit;
    		prev=prevLink; 
    		next=nextLink; 
    		
    	}
    	
    	
    	public E returnData()
    	{
    		return data; 
    	}
    	
    	
    	
    	public Node<E> returnLinkNext()
    	{
    		return next; 
    	}
    	
    	public Node<E> returnLinkPrev()
    	{
    		return prev; 
    	}
    	
    	
    	public static <E> int length(Node<E> head)
    	{
    		Node<E> cursor; 
    		int count = 0; 
    		
    		for(cursor = head; cursor != null; cursor = cursor.next )
    		{
    			count++;
    		}
    		
    		return count; 
    	}
    	
    	 
    	public void addHead(E element)
    	{
    		prev = new Node<E>(element,null,prev); 
    		 
    		
    	}
    	
    	
    	public void setLinkNext(Node<E> node)
    	{
    		
    	}
    	
    	
    	public void setLinkPrev(Node<E> node)
    	{
    		prev = node; 
    		
    	}
    	
    	
    
    	
    	
    	
    }
    Thank you for any help.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default Re: Doubly Linked List. How to add to the head.

    How do I assign its next link to the old head?
    Where is the value of the "old head"?

    Where is the definition for the linked list class? How can a node change the pointers in the linked list? Shouldn't the linked list class take care of that?
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Doubly Linked List. How to add to the head.

    Sorry, the linked list is going to be implemented as a Deque. I assume this is what you're referring to?
    head = null;
    tail = null;

    Java Code:
    public class Deque<E> implements SuperDeque<E> {
    	Node<E> head;
    	Node<E> tail;
    	
    	 public Deque()
    	 {
    		 head = null;
    		 tail = null; 
    	 }
    	
    	//AddFirst method
    	public void enqueueFront(E element) {
    		System.out.println(isEmpty()); 
    		if(isEmpty())
    		{
    			head = new Node<E>(element,null,null); 
    			tail = head; 
    		}
    		
    		else
    		{
    			head.addHead(element);
    			head = head.returnLinkPrev();
    			tail = head.returnLinkNext(); 
    			
    			
    		}
            
    	}
    
    	//AddLast Method
    	public void enqueueBack(E element) {
    		//(Data, rear link, front link) 
    		tail = new Node<E>(element,tail,null); 
    		
    	}
    
    	//PeekFirst Method
    	public E peekFront() throws DequeUnderflowException {
    		if(isEmpty()) return null; 
    		
    		else return head.returnData(); 
    		
    	}
    
    	//PeekLast Method
    	public E peekBack() throws DequeUnderflowException {
    		if(isEmpty()) return null; 
    		
    		else return tail.returnData(); 
    	}
    
    	//RemoveFirst Method
    	public E dequeueFront() throws DequeUnderflowException {
    		E data; 
    		
    		if(isEmpty()) 
    		{
    			tail = new Node<E>(null, head, head); 
    		}
    		
    		else 
    		{ 
    		    data = head.returnData();
    			head = head.returnLinkNext(); 
    		}
    		
    		return null; 
    		
    	}
    
    	//RemoveLast Method
    	public E dequeueBack() throws DequeUnderflowException {
    		E data; 
    		if (isEmpty()) return null;
    		
    		else
    		{
    			data = tail.returnData(); 
    			tail = tail.returnLinkPrev(); 
    		}
    		
    		return data; 
    	}
    
    	@Override
    	public boolean isEmpty() {
    		if(Node.length(head) == 0) return true; 
    		else return false; 
    		
    	}
    
    	@Override
    	public int size() {
    		return Node.length(head); 
    	}
    
    	@Override
    	public void clear() {
    		head = null;
    		tail = null; 
    		
    	}
    
    	@Override
    	public boolean equals(Deque<E> other) {
    		// TODO Auto-generated method stub
    		return false;
    	}
    	
    	
    	
    
    }

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default Re: Doubly Linked List. How to add to the head.

    Why is the addHead method in the Node class?
    Shouldn't the list changing methods be in the class that holds and controls the list?
    If you don't understand my response, don't ignore it, ask a question.

  5. #5
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Doubly Linked List. How to add to the head.

    I have a enqueueFront method in the deque class. I am using another node class as a guide and it has this method in it

    Java Code:
    public void addNodeAfter(E element)   
       {
          link = new Node<E>(element, link);
       }
    I figured that I could modify that method to suite my needs.

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default Re: Doubly Linked List. How to add to the head.

    I'd take all of the list changing code out of the Node class.
    If you don't understand my response, don't ignore it, ask a question.

  7. #7
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Doubly Linked List. How to add to the head.

    Ok, so basically anything that modifies the list I should put into the Deque class? Would this make it easier to reference the tail, which is defined in Deque?

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default Re: Doubly Linked List. How to add to the head.

    Yes, I think the code that does changes to the list should be in the class that defines the list.
    If you don't understand my response, don't ignore it, ask a question.

  9. #9
    Wnt2bsleepin is offline Senior Member
    Join Date
    Feb 2012
    Posts
    219
    Rep Power
    3

    Default Re: Doubly Linked List. How to add to the head.

    I think I got it. I removed the addhead function all together and just changed the code around a bit in the Deque class.

    Java Code:
    public void enqueueFront(E element) {
    		System.out.println(isEmpty()); 
    		if(isEmpty())
    		{
    			head = new Node<E>(element,null,null); 
    			tail = head; 
    		}
    		
    		else
    		{
    			
    			head = new Node<E>(element,null,head); 
    			
    			
    		}
            
    	}
    That seems to give me a list length of 2 and I can successfully print out the contents of the list with a for loop. Thanks for your help.

  10. #10
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,308
    Rep Power
    25

    Default Re: Doubly Linked List. How to add to the head.

    You're welcome.
    If you don't understand my response, don't ignore it, ask a question.

Similar Threads

  1. Doubly Linked List removing help?
    By Bungkai in forum New To Java
    Replies: 0
    Last Post: 12-02-2011, 06:58 AM
  2. Doubly-Linked list
    By swp in forum New To Java
    Replies: 3
    Last Post: 10-11-2011, 03:27 PM
  3. help me on this: circular doubly linked list
    By someone in forum New To Java
    Replies: 13
    Last Post: 04-11-2011, 10:57 AM
  4. Doubly Linked List
    By matin1234 in forum New To Java
    Replies: 0
    Last Post: 06-02-2010, 05:58 AM
  5. Help with Doubly linked list
    By Dr Gonzo in forum New To Java
    Replies: 5
    Last Post: 12-06-2008, 07:45 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
  •