• Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help with method for Circular Doubly Linked List  RSS feed

 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For the program I have to create, I need to be able to work with the elements of a circular doubly linked list to do the following:

Find an element in the list (specified as an argument)
Insert an element after a specified element (specified as an argument)
Delete an element (specified as an argument)
Display the elements in the list

I can insert elements and display the elements, but I can't figure out how to search for an element, insert an element after a specified element, or delete an element.

What I am having trouble with is passing the elements in the list as arguments for searching, deleting, inserting after an element.



If anyone could give me some insight into how to solve my issues, I would greatly appreciate it.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First off, you could choose better names. For example, the name "dLL" does nothing to convey its intent/use at all. It took me a while reading and analyzing the code to figure out that it points to the head Node of the list. A better name would be just that, head. That greatly lightens the conceptual load on whoever reads the code. Be kind to others, choose intention-revealing names.
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One piece of advice we commonly give around here is to step away from the computer, take pencil and paper and draw and/or write out the procedure in plain English. Pretend you are teaching a ten-year old to do this manually. How would you describe the process in a step by step manner? Once you have that, it's usually an easier process to translate it into code.

Give it a shot with your find method and show us what you come up with.
 
Steve Fahlbusch
Bartender
Posts: 612
7
Mac OS X Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Greetings Mike,

First and mostly, please follow what Junilu suggested - it is really important that you understand the data structure before you implement it.

Next, (a really nice hint) if you understand the data structure,then create a null node as your head/tail pointer (i.e.: null data, next points to itself, prev points to itself). If you don’t understand this - don’t worry, just saving you edge case issues.

Understand that all (most) actions in a DLL are done via the current pointer location, so you may want to implement a few methods that manipulate the current pointer - like move next, move prev, move head, move tail, delete (or remove), insert after, note: now an insert prev can be a move prev, insert after.

All that said, there is some issue with the requirements as you said vs the code. Ok the data reference you are using is an int, but the delete seems to be the ‘index’ and not the contents. You need to resolve that.

So to sum up: you can write a few (bunch) of helper methods that you or may not expose to users of your main class that you can use to help you. Like: a print all could be:
moveToHead(), getSize(), while (size>0), getAtPointer(), print(), moveNext(), size— [end while]

Take some time to fully understand double linked lists - then (with pencil and paper) design your code, then and only then start coding.
 
Mike Stein
Ranch Hand
Posts: 33
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Okay, so this is what I finally came up with for the linked list. I am still learning so I am well aware that my code isn't as clean or efficient as it should be. If you guys could look it over and possibly give me any suggestions to make it look and work better that would be fantastic. Also, thanks guys for the tips. I found that stepping back and writing down the nodes helped me to visualize what was going on.

 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One thing I would do is try to eliminate duplicate code. There's some there where you are trying to find a particular node based on the value. Also, I would throw RuntimeExceptions instead of using System.out.println for errors. Client code, like a static main method, can catch the exception and display a user-friendly message.

In pseudo code:
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you have a bug in this code. What happens when you add some nodes, then remove all the nodes, and then try to add a new node?
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Look over this code and see if there are things you like better:
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And here are the JUnit tests for it:
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!