Results 1 to 10 of 10
- 04-01-2012, 08:09 PM #1
Senior Member
- Join Date
- Feb 2012
- Posts
- 219
- Rep Power
- 10
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; } }
- 04-01-2012, 08:35 PM #2
Re: Doubly Linked List. How to add to the head.
How do I assign its next link to 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.
- 04-01-2012, 08:47 PM #3
Senior Member
- Join Date
- Feb 2012
- Posts
- 219
- Rep Power
- 10
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; } }
- 04-01-2012, 08:55 PM #4
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.
- 04-01-2012, 09:16 PM #5
Senior Member
- Join Date
- Feb 2012
- Posts
- 219
- Rep Power
- 10
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); }
- 04-01-2012, 09:24 PM #6
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.
- 04-01-2012, 09:48 PM #7
Senior Member
- Join Date
- Feb 2012
- Posts
- 219
- Rep Power
- 10
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?
- 04-01-2012, 09:51 PM #8
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.
- 04-01-2012, 10:31 PM #9
Senior Member
- Join Date
- Feb 2012
- Posts
- 219
- Rep Power
- 10
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); } }
- 04-01-2012, 10:37 PM #10
Similar Threads
-
Doubly Linked List removing help?
By Bungkai in forum New To JavaReplies: 0Last Post: 12-02-2011, 06:58 AM -
Doubly-Linked list
By swp in forum New To JavaReplies: 3Last Post: 10-11-2011, 03:27 PM -
help me on this: circular doubly linked list
By someone in forum New To JavaReplies: 13Last Post: 04-11-2011, 10:57 AM -
Doubly Linked List
By matin1234 in forum New To JavaReplies: 0Last Post: 06-02-2010, 05:58 AM -
Help with Doubly linked list
By Dr Gonzo in forum New To JavaReplies: 5Last Post: 12-06-2008, 07:45 AM
Bookmarks