Skip to main content
GameDev.net gamedev.net
🔒 Locked

Linked Lists and Caterpillars

Started by toXic1337 Nov 1, 2006 at 3:51 PM 5 replies 1.4k views
Original Post
toXic1337
toXic1337
Hello, I'm messing around with linked lists in "Nibbles" type game I'm making and I've run into a problem. I'm wanting to join two caterpillars together, in other words, concatenating one linked list to the end of another. My lists are set up so that the first node is private and there is a method to add nodes to the beginning of the list only. They aren't java LinkedLists or anything of that sort, my class is completely home made. I have a concat method as follows: 

public void concat(LinkedList other)
{
    //go to the end of private variable first and add
    //other to the end of it, in other words, find last.next
    //and set it equal to others first node.
}
I thought about converting them both to arrays, concatenating using memory copy commands and then reconstructing a new linked list from this array, since one of my constructors for the linked list takes an array of objects (segments) and constructs a linked list perfectly. Anyway, didn't know if any of you had a good algorithm for linked list concatenation, but I thought I'd ask anyways. Thanks, toXic1337~
toXic1337
Agony
Agony
Well, with access to all data members, you should be able to do something similar to this pseudocode:
void Concatenate(LinkedList other){  if (other.head != null)  {    //The other list is not empty, so we have to    //move the items from that list to this list    if (head != null)    {      //This list is also not empty, so we know we      //have a tail, and any appended items must be      //inserted after this tail      //Find the tail, if we don't already have a      //reference to it      Node tail = head;      while (tail.next != null)      {        tail = tail.next;      }      //append the other list to the end of this list      tail.next = other.head;      //make the beggining of the other list point to      //the last item of this list      //note that this is not used if you have a singly-      //linked list      other.head.prev = tail;      //remove the reference of the items from the other      //list, so that this list holds the only reference      other.head = null;    }    else    {      //This list is empty, but the other list has items,      //so all we need to do is steal the other list's      //items      //Set our head to the first item in the other list      head = other.head;       //remove the reference of the items from the other      //list, so that this list holds the only reference      other.head = null;    }  }  //else is not needed, because if the other list  //has no items, then appending its items onto the  //end of this list is a no-op, whether or not this  //list has items}


This is one of the benefits of linked lists: Splicing is a simple, constant time operation, no matter how large the lists are, or how complicated the objects in the list are.
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas nly, and not for things themselves." - John Locke o
toXic1337
toXic1337
What would you do given that you don't have public access to other's head. I know I could just make it public, but I'm looking for a harder way so I develop other algorithmic skills. Let's say that I only have a means of finding values at positions in a public method, no direct access to the head or any member data for that matter.
toXic1337
Agony
Agony
Quote:
Original post by toXic1337
What would you do given that you don't have public access to other's head. I know I could just make it public, but I'm looking for a harder way so I develop other algorithmic skills. Let's say that I only have a means of finding values at positions in a public method, no direct access to the head or any member data for that matter.

I may be wrong, since I haven't used Java enough to become very familiar with it's nuances, but at least in C++, two objects of the same type have access to each other's private members, so public/protected/private don't describe boundaries between objects, but instead describe boundaries around types. Try assuming that you have access to the other list's private details, and see if it compiles/runs with no errors.

If so, I'd say that there is nothing wrong with doing it this way. In fact, it's vitally important that you can do it this way, because it allows for much greater efficiency, without having to expose certain details publicly to other types. Encapsulation is suppose to hide details of how and object works, so that other types don't need to know those details. If a LinkedList knows how a LinkedList works (obviously it does), then a LinkedList should be granted access to all of the intimate details of any LinkedList.
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas nly, and not for things themselves." - John Locke o
Simian Man
Simian Man
Java is like that to (I was not sure, so I just tried it). Here is the code I tried:
class A{	private int a = 7;	public int add( A other )	{		return a + other.a;	}}public class temp{	public static void main(String[] args)	{		A a1 = new A( );		A a2 = new A( );		System.out.println( a1.add( a2 ) );	}}


Compiles fine, so you should have no problem [smile].
Zekeva
Zekeva
Actually because they're both instances of the same class, they have access to each other's private members. This is also seen in a standard overridden equals method. The following (incomplete) equals method shows this:

class Foo {  private String bar;  public boolean equals(Object o) {      Foo other = (Foo) o; // cast to make my point clearer      return this.bar.equals(other.bar); // @  }}


See at the @ I have accessed other.bar which is private. I normally couldn't do this but because they are instances of the same class, you can.

I find it kind of weird that it was designed like this. Taking the word Private at face value means (to me) only the owner should be able to see it but this is clearly not the case. The comparison of object boundary vs. type boundary made by Agony is a good one.

I'd also be interested to know why you aren't using the built-in linked list as concatenation is very easy to do (addAll, I think).

Edit: Two people beat me to it whilst I was figuring out how to format my code properly. But hey you get the point.

Z
Good, fast, cheap. Pick any two.
toXic1337
toXic1337
Thanks for bringing that comparison to view Agony, rating++. I never would have even tried that assuming that objects private members are exclusive to only that object. Thanks again, you've all been a lot of help.

P.S.: I'm not using the built in linked list classes of java because I'm doing this as a learning experience, not necessarily just to make a game.
toXic1337

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.