• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Doubly Linked List

 
Ranch Hand
Posts: 42
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mark Nibert
Ranch Hand
Posts: 42
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mark Nibert
Ranch Hand
Posts: 42
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Jesper de Jong
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oracle's Java Tutorials is a good place to start learning Java. Especially look at the Covering the Basics trails.
 
Sheriff
Posts: 22821
132
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mark Nibert wrote:I understand what a linked list is and can understand the logic it is just implementing it in java that is harder for me.


Then here's a good trick: first right it down in pseudo code, and then try to translate that, in small pieces, to Java.
 
Mark Nibert
Ranch Hand
Posts: 42
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?


 
Ranch Hand
Posts: 222
Google Web Toolkit Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Mark, welcome to JavaRanch!

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!
 
Mark Nibert
Ranch Hand
Posts: 42
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I will try that and see what I come up with.
 
Rob Spoor
Sheriff
Posts: 22821
132
Eclipse IDE Spring Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic