I am working on a program for a doubly linked list that allows for forward and backward links and the content of the node needs to be an object. I also need to allow for insert, delete, getPrev and getNext. I have the Introduction to Algorithms book (3rd edition) and I read up on linked lists. I think I kind of understand how to write it out but I am not sure. Does anyone know of any good sites or links that would help me complete this task? I am very new to programming and just have recently got back in to it after a break from work.
What exactly are you not sure about? Did you write some code already? Did it work, or not? You learn programming by experimenting - write code, see if it works, and if it doesn't then learn how to fix it.
I have been using google, I just dont know what I am looking for and it is making it a lot harder. I appreciate the response and will look at the links you sent...I am not a good programmer at all and this is tough for me.
Joined: Jul 01, 2009
Jesper de Jong wrote:What exactly are you not sure about? Did you write some code already? Did it work, or not? You learn programming by experimenting - write code, see if it works, and if it doesn't then learn how to fix it.
I am a terrible programmer, I barely have the basics down and I am being tasked w/ this program and I am just having trouble getting it started. I understand what a linked list is and can understand the logic it is just implementing it in java that is harder for me.
I know that for a doubly linked list it is going to allow for forward and backward searching of a list of objects instead of only going in one direction like a singly linked list. I know that it will have a head and tail and I will need to create a node pointer for prev and next. If the prev node does not point to anything that would be the head and if the next node is empty and does not point to anything then it is the tail. This is the part that I am not sure on how to set up in Java. Do I need to make the nodes of type Object?
First of all, yes, Link class that you put by default extends Object class, everything in Java except primitive types extend Object class.
However for your given exercise, I would recommend you not to look anywhere for ready code, but try to code everything yourself using pseudocodes from intro to alg. book. I remember having the exercise with doubly linked lists myself, and it was a good experience to be able to do it myself, I learned a lot.
As of hint, think of following: first you would put your Link list to data structures, that would be Link objects, referencing each other. Now think what will happen with every link, and more precisely with connections of those Links, when there is a delete and insert. Try to draw Links and connections between them with pencil on paper, and then erase and reconnect nodes, this will help!
You may be able to use one single object for the head and tail. The next element is the first element, the previous element is the last element. You'll need to differentiate this element from the rest. I believe LinkedList does this by storing a reference to the head and then using == to compare nodes against the head node.
At this risk of possibly adding more confusion.... you could make the code much easier by making a circular linked list where you start our with a special node that points to itself (both next and prev). You then dont need to worry about all of the boundary conditions in your add and delete methods (ie: adding at head, adding at tail, adding at head and tail all resolve to the nominal case - adding between two nodes). --- same with delete.