Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
The moose likes Java in General and the fly likes Inserting elements along a LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Inserting elements along a LinkedList" Watch "Inserting elements along a LinkedList" New topic
Author

Inserting elements along a LinkedList

Logan Wilson
Greenhorn

Joined: Sep 21, 2012
Posts: 17
I'm trying to figure out where my logic is screwy on this. I've been playing around with examples, and I'm trying to traverse a self-made linkedlist, remove an element of my choosing, and reinsert it at the point of my choice. So far, I can't figure out how to move something from the head towards the tail (not using a double linked list) or how to keep my element count correct.

my linklist node constructor is pretty basic:



This is my main method/driver program: it's where all my trouble is.



This is my manager method:


This is what my current output looks like right now.

10: J
9: II
8: HHH
7: GGGG
6: FFFFF
5: EEEEE
4: DDDD
3: CCC
2: BB
1: A
-------------------
looking at
8: HHH
skipping
7: GGGG
-------------------
4: GGGG
10: J
9: II
8: HHH
6: FFFFF
5: EEEEE
4: DDDD
3: CCC
2: BB
1: A
-------------------
looking at
8: HHH
skipping
6: FFFFF
-------------------
4: GGGG
8: FFFFF
10: J
9: II
8: HHH
5: EEEEE
4: DDDD
3: CCC
2: BB
1: A

Any pointers on which way to take it? I'm thinking there's a better way instead of referencing my "i" index variable, but I'm still not sure how to keep the elements properly numbered. It's my goal to eventually reference these link list nodes and populate a gui JButton array with the contents.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38107
    
  22
Why have you got those three fields in your node class? Your mode class should have three fields: Foo value, Node next and Node previous. Note when you start your List, and add the first node, its next and previous fields will both point to null, and there will always be two null values, one at each end of the List. This means you need to test for nullity whenever you use those fields, otherwise you might suffer a NullPointerException. Rather than using a Foo reference, you would have a Team field.
I think you are trying too much at once. You ought not to try reading a file, creating a List, and altering the List all at once. You ought also to do those things in different methods, preferably in different classes. Your List exists to contain the data, not to read the file.
Do you understand how a doubly‑linked list works? It is like thisThe List class holds a reference to the head and tail, and each node has a reference to the nodes adjacent to it. For the head and tail nodes, that will be null. When you have an empty List, the head and tali nodes will be null, and when you start your List and it has one element, that one node is both head and tail simultaneously.
Your List class can also hold a reference to a “current” node, and you can use that, or the head or the tail, to search the List, depending which is closest to what you are seeking.
Removing a node in the middle is fast; you simply make the next and previous of the nodes adjacent to it point to each other.
Adding a node in the middle is fast too, as long as you have a reference to where you intend to add it. When you add a node, you must make the nodes adjacent to it point to that new node and vice versa. All the next and previous fields must line up in a row, and the order should be maintained whether you go forwards or backwards. Can you understand this paragraph? I don’t think I have been very clear.
Finding a node is slower; it runs in linear time because you have to go from node to node.
Moving a node would be slower still. So you don’t move nodes at all. You remove them, record the reference to the value, and then add a new node in the desired location.

I think the node class should be a private inner class of the List class, but that might be too complicated for “beginning”

Do your project in stages. Get your List working first. Try it out with something simple like ints first. Then change it to Team. Then add the file reading. Then change the List to a parmeterised type List<T> and use it as a List<Team>.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38107
    
  22
There is another discussion about linked lists which you might find useful: here.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7554
    
  18

Logan Wilson wrote:So far, I can't figure out how to move something from the head towards the tail (not using a double linked list) or how to keep my element count correct.

Well, there's a few things going on:

1. If, by your "element count" you mean the num field in your Node: generally, you don't. A linked list is a dynamic structure, and introducing a "this is my position in the list" field is fraught with difficulties. For one thing, if you insert a Node, you have to update all the numbers that follow it, which is likely to be a very expensive operation; and in a multi-threaded environment, it also has to be synchronized. You just have to accept that finding a Node #n that is not at the beginning or the end of the list takes O(n) time.

2. Forward Linked lists look nice and simple, but their operations aren't. Specifically, if you are positioned at a particular Node, you can only do something that affects the List (ie, add, remove a Node) on the Node that follows it. Specifically:
  • You can only add a Node after the one you're on.
  • You can only remove the Node after the one you're on.
  • so, in order to remove Node n, you need to position to Node n-1.

    The only exception to this is that you can generally add a new first Node in O(1) time.

    You should also be aware that backwards traversal of a forward linked list is, to all intents and purposes, impossible. Or rather, it takes so long that you might as well not provide it.

    HIH

    Winston


    Isn't it funny how there's always time and money enough to do it WRONG?
    Articles by Winston can be found here
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    Thanks, Winston. I'm really discovering it's a pain in the butt to try all that stuff. I did mean the element "num" on each one, and it is more trouble then it's worth.

    Campbell, it makes sense what you were saying. I started making things work, and then I kept piling more and more stuff on top.

    It's ok, I'm studying up on doubly linked lists, and it's making a lot more sense on how to shift things around. I'm guessing once I get the foundations of that set, then it's just a matter of mapping JButtons to the list and refreshing them everytime I want to visually shift things around.

    Thanks for all the pointers!
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Logan Wilson wrote:TI'm guessing once I get the foundations of that set, then it's just a matter of mapping JButtons to the list and refreshing them everytime I want to visually shift things around.


    I don't do Swing, so I don't know if it makes sense to store a list of buttons. However, when you are ready to actually use a list "for real" (rather than just writing one for the educational exercise, which is a worthwhile task in its own right), be aware that the core API includes java.util.LinkedList and java.util.ArrayList. You'll want to use those rather than rolling your own, unless you need special functionality that they don't offer.
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    Jeff Verdegan wrote:
    I don't do Swing, so I don't know if it makes sense to store a list of buttons. However, when you are ready to actually use a list "for real" (rather than just writing one for the educational exercise, which is a worthwhile task in its own right), be aware that the core API includes java.util.LinkedList and java.util.ArrayList. You'll want to use those rather than rolling your own, unless you need special functionality that they don't offer.


    It's not that I'm needing a special function, it's that we're being made to shy away from the pre-built classes and work on creating our own models.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    I thought that is what you had to do. The technique of getting a bit to work and then piling on sounds good. As long as you only pile a few bits on before you test it all again.
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    well, I've got the idea diagrammed out on paper and it makes perfect sense on how I can talk it through with pseudo code, but I'm just not getting it to pull out and reinsert a link at a specified point. I did like you said Campbell, and stripped all if it down to just a set of links with just some String names in it. Now, I've tried setting it up with two positions, (say 7 and 5). I want to grab the linklist at position 7 and move it into position 5. I figured, it's going to be a for list to count down to the position 6, grab the next address for position 7, assign that address to a tempNode, connect position 6 to position 8, and reassign my tempNode to position 5.

    To assign it to position 5, I'm using a for list again to look for position 4, assigning the tempNode to the .next address of position 4, assign the tempNode.next address to the current.next.next address (to connect tempNode to position 6). But, I'm either removing ALL the elements except the last 4 positions, OR I've been stuck in a loop printing out the elements being switched.

    arrg.....I'm betting it has something to do with improperly assigning that "to" tempNode I'm using. Any more pointers?
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    I'd suggest drawing pictures and writing down the steps very precisely.



    Then you figure out the code you need that corresponds exactly to each step you've written down.

    If the code isn't doing what you epxect it to do, print out the next pointer and the data at the node it's pointing to at each step, so that you can compare the real picture to the expected picture.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    Jeff Verdegan wrote:I'd suggest drawing pictures and writing down the steps very precisely.
    Good idea.

    Jeff has simplified the diagram a little, by missing out the previous fields. Remember each node points backwards, tooOn my keyboard I can get arrows with AltGr-Y← AltGr-I→ AltGr-U↓ and Shift-AltGr-U↑. But I am not using Windows.

    If you have difficult implementing that move method, try implementing insert methods and remove methods. Actually, the List interface calls its method add, so I shall say add rather than insert:-Suggested pseudo-code for addSuggested pseudo-code for removeYou can implement a move method with a combination of add and remove. Beware. If you remove element 4 and then try to insert it at element 6, you may be one too far to the right. You may have to implement move(4, 6) by a combination of remove(4) and add(5, value). You can confirm that by drawing a diagram. And that is where we came in!
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Campbell Ritchie wrote:
    Jeff Verdegan wrote:I'd suggest drawing pictures and writing down the steps very precisely.
    Good idea.

    Jeff has simplified the diagram a little, by missing out the previous fields. Remember each node points backwards, too[code]


    In the OP he mentioned that is was a singly-linked list. If that changed, my bad for not noticing.
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    Jeff Verdegan wrote:

    In the OP he mentioned that is was a singly-linked list. If that changed, my bad for not noticing.


    No, it's stayed the same. I'm still struggling trying to figure out the mechanics. I'm becoming well aware of null-pointer exceptions, which is driving me batty also. I'm going to keep diagramming it and changing my coding as I go along.

    Best part is, the only thing that gets hurt is 1's and 0's, right?
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    Is it a singly‑linked list? Sorry, I thought it was doubly‑linked. If it is singly‑linked, then you do not have the previous fields, nor do you have the tail reference. Only a head reference.
    Advantage: you can reduce the number of steps in adding, removal, etc.
    Disadvantage. You can only find nodes by going forwards from the head node (No 0) or the “current” node. I still think moving a node is better done by a combination of removal and adding. To move the No 14 node to position 10 when your “current” node is No 12:
  • 1: Go forward 2 nodes to No 14.
  • 2: Record that node temporarily.
  • 3: Reset the “current” node back to the head node No 0.
  • 4: Move 9 places to No 9.
  • 5: Insert the previous No 14 node after No 9.
  • You can see that finding a value in the List requires linear time, whereas finding a value in an array‑based List would take constant time (i.e. much faster).

    I would suggest you put something in your loop to test for nullityYou may consider another approach, which is to test for the index sought before looping. If the index sought ≥ Node.getSize(), you can throw an Exception.
    Winston Gutkowski
    Bartender

    Joined: Mar 17, 2011
    Posts: 7554
        
      18

    Logan Wilson wrote:I'm still struggling trying to figure out the mechanics. I'm becoming well aware of null-pointer exceptions, which is driving me batty also.

    Welcome to programming. If you decide to keep doing it you'll have many more of those ahead of you.

    Another little point for you: I notice that your Node is called a "TeamNode" and that it expects to hold a String. With Generics you can allow it to hold anything you like, viz:Then, whenever you need a new Node that holds a String, you can simply write:
    LLNode<String> newTeamNode = new LLNode<String>("aTeamName", anotherNode);

    And the nice thing about that is that if you later create a Team class to hold information about a team, the line becomes:
    LLNode<Team> newTeamNode = new LLNode<Team>(aTeamObject, anotherNode);

    Notice that I made the Node fields private. I'd advise you to get into this habit with ALL the classes you write:
    DON'T make fields public. Make them private and provide methods to get and set them.

    Also, depending on where you define your LLNode class, you may also want to make its constructor private or package-private, because you don't really want just anyone creating Nodes wherever they like.

    HIH

    Winston
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    Winston Gutkowski wrote: . . . depending on where you define your LLNode class, . . .
    Would you ever make it anything but a private inner class of the LinkedList class?

    I resisted the temptation to say inner classes earlier because of the risk of information overload.
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    Campbell Ritchie wrote:Is it a singly‑linked list? Sorry, I thought it was doubly‑linked. If it is singly‑linked, then you do not have the previous fields, nor do you have the tail reference. Only a head reference.
    Advantage: you can reduce the number of steps in adding, removal, etc.
    Disadvantage. You can only find nodes by going forwards from the head node (No 0) or the “current” node. I still think moving a node is better done by a combination of removal and adding. To move the No 14 node to position 10 when your “current” node is No 12:
  • 1: Go forward 2 nodes to No 14.
  • 2: Record that node temporarily.
  • 3: Reset the “current” node back to the head node No 0.
  • 4: Move 9 places to No 9.
  • 5: Insert the previous No 14 node after No 9.
  • You can see that finding a value in the List requires linear time, whereas finding a value in an array‑based List would take constant time (i.e. much faster).



    Well, after further playing around, I'm getting closer. I'm loosing my temp node address variable though, and it keeps getting deleted. Somehow, I'm screwing around and not capturing it like I thought. I'm betting, it's a multi-step process instead of keeping it simple like I tried. I tried enclosing all my calls into brackets under my for loop, but it either forced a recursion or it deleted every 2 element on the list.

    Ahh....oh well, I can at least look positively on this whole thing. I'm really learning a ton about this stuff.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Sounds like you need to do more fine-grained drawing and printing to see where the discrepancies lie.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    It is worth it for the learning.
    Yes, moving something in a linked list is a multi‑step process. You should already have methods likeThat list is not exhaustive nor definitive, but arranged in order of difficulty, easiest first (I think). You might do well to go and find the java.util.List interface and make your method names match that.
    The nice thing about a multi‑step process is that you can break it down. Divide and rule. Then put the parts back together. Writing those methods will create the parts for the multi‑step move(int fromIndex, int toIndex) method.
    Jeff Verdegan
    Bartender

    Joined: Jan 03, 2004
    Posts: 6109
        
        6

    Campbell Ritchie wrote:It is worth it for the learning.
    Yes, moving something in a linked list is a multi‑step process. You should already have methods like
    ...
    You might do well to go and find the java.util.List interface and make your method names match that.


    Note that there's one fundamental difference between this model and that of java.util.List. Here, our list has notions of a "current index" and "current value". That is, the index of the element we're currently looking at as we traverse the list, and the value at that index. In the case of java.util.List, it doesn't have that. Rather, there's a separate type called an Iterator that is responsible for traversing the list.

    The model Campbell shows here, with the list managing its own traversal, may be simpler to write, and it may be how your instructor is teaching lists. (That's how it was taught when I learned, back when computers were made of dirt.)

    You don't need to worry about the details of the difference right now. I just wanted to point it out in case you do use java.util.List for a model, so that you don't get confused when you see an iterator() method but no getCurrentIndex() and getCurrentValue() methods.
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    Jeff Verdegan wrote: . . . when computers were made of dirt. . . .
    As opposed to nowadays, where I occasionally stumble upon websites where the programming is made of dirt?
    Actually, I think computers are made of sand, which is presumably where the silicon comes from.

    I think the technique to find a current‑plus‑one node and the technique behind the next() method of an Iterator will be the same
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    you guys are awesome!

    I've got the moves all figured out now, and it's working well. The only part I'm stumbling over now, is trying to figure out how to get the string values from my linked list nodes onto a JButton. I keep getting my list populated with 20 null string values.
    Logan Wilson
    Greenhorn

    Joined: Sep 21, 2012
    Posts: 17
    Here's the link to my updated code with the new difficulty. (always something, right?)

    I'm still reading in a file, but it's just "A, B, C" stuff.

    http://www.coderanch.com/t/594894/GUI/java/do-JButton-string-linkedlist-value#2712120
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 38107
        
      22
    Logan Wilson wrote:you guys are awesome!
    You’ve got us all embarrassed, now.
    I've got the moves all figured out now, and it's working well. . . .
    Brilliant. And you know lots about linked lists, which will come in useful when you least expect it.
     
    wood burning stoves
     
    subject: Inserting elements along a LinkedList
     
    Similar Threads
    LinkedList
    on calling methods..
    do while help
    Liked List help
    stuck trying to swap values in JButtons