Sign in to follow this  
Followers 0

[Java]Linked List Implementation

19 posts in this topic

Posted

Hello all,

I am in a computer science class for part of my degree, but I cannot grasp how to implement linked list in Java. I know how to in C and C++, however this one for some reason is hard for me to grasp. I am supposed to be making a class that stores an address, with two constructors (one for an apartment number and one without). I thought it would be good to use a linked list on this one rather than an array.

 

I haven't finished the Address class yet, but so far this is what I have:

import java.util.*;

public class Address {
	private int houseNumber, aptNumber, zipCode;
	private String Street, City, State;
	
	private Address next;
	private int count = 0;
	
	public Scanner in;
	
	// Not an apartment
	public Address(){
		in = new Scanner(System.in);
	}
        // functions to request data, because I hate having to make more variables.
	public String Street(){
		System.out.println("Please input street name: ");
		return this.in.nextLine();
	}
	public int HouseNum(){
		System.out.println("Please enter street number: ");
		return this.in.nextInt();
	}
	public String City(){
		System.out.println("Please input city name: ");
		return this.in.nextLine();
	}
	public int AptNum(){
		System.out.println("Please enter apartment number: ");
		return this.in.nextInt();
	}
	public int ZipCode(){
		System.out.println("Please enter zip code: ");
		return this.in.nextInt();
	}
	public Address(int houseNum, String street, int zip, String city, String state) {
		this.houseNumber = houseNum;
		this.Street = street;
		this.zipCode = zip;
		this.City = city;
		this.State = state;
		this.aptNumber = 0;
		in = new Scanner(System.in);

	}
	// An apartment
	public Address(int houseNum, String street, int zip, String city, String state, int aptNum){
		this.houseNumber = houseNum;
		this.Street = street;
		this.zipCode = zip;
		this.City = city;
		this.State = state;
		aptNumber = aptNum;
	}

}

As you can see, I have no idea what I am doing for linked list. I know that she didn't specify to use it, nor have we had any instruction on it yet but I think it's the most practical way. Long story short, I spent 8 hours last night reading about linked list (with many different types) rather than completing the assignment.

 

Any help explaining to me how to implement a linked list in java would be helpful!

Share this post


Link to post
Share on other sites

Posted

The code you showed has nothing to do with a linked list, it's just some sort of record with methods for getting user input. Since you say that you know how to implement a linked list in C or C++, how would you do it in these languages? What Java-specific concept is preventing you from translating that knowledge in Java?

 

I get the feeling that you're confusing the type of element you want to store in the linked list with the linked list implementation itself - which should be agnostic to what type of element it holds.

Share this post


Link to post
Share on other sites

Posted

The code you showed has nothing to do with a linked list, it's just some sort of record with methods for getting user input. Since you say that you know how to implement a linked list in C or C++, how would you do it in these languages? What Java-specific concept is preventing you from translating that knowledge in Java?

 

I get the feeling that you're confusing the type of element you want to store in the linked list with the linked list implementation itself - which should be agnostic to what type of element it holds.

Pointers...

Share this post


Link to post
Share on other sites

Posted

Pointers...

 

Pointers are implicit.

 

Basically, you have:

public class Address {
private int houseNumber, aptNumber, zipCode;
private String Street, City, State;
 
private Address next;
}

Now create a linked list!

Address head;
 
public void AddBeginning(int houseNum, ...){
    Address a = new Address(houseNum, ...);
    a.next = head;
    head = a;
}

Share this post


Link to post
Share on other sites

Posted

You can think of the 'next' field as a pointer (which is a reference in Java, as in, a reference to another Address object).

 

C++:

class LinkedObject {
public:
  LinkedObject* next;
}

Java:

public class LinkedObject {
  public LinkedObject next;
}

Share this post


Link to post
Share on other sites

Posted

Pointers...

Every variable is a pointer in Java except for basic numeric types (int, float, etc.). The difference with C is that it's an opaque pointer; you can't know the address it points to; but implementing something like a linked list is exactly the same.

Share this post


Link to post
Share on other sites

Posted

Thank you all! I shall write something up after work today.

Share this post


Link to post
Share on other sites

Posted

Java has two types of variables, a primitive, which is your standard int, float, char, etc, and the reference type, in which instances of classes, otherwise known as objects, are stored.

 

A linked list can be implemented in a generic or adhoc manner. There's no rule stating that all linked list implementations must be generic.

 

Chaining a set of Address objects seems reasonable.  If I might offer some advice though, I wouldn't implement the input reading functions directly in the class for a couple of reasons, mainly involving code reuse and maintainability - 1. If the source of the input changes, or multiple sources are required later, you'd have to modify the class itself every time to accommodate the different inputs. Instead, I'd implement accessor functions, which can verify / format the information, and call those from outside of the class. A single implementation that can accept the input from any source. 2. I'd create a container class for the list itself where you can encapsulate helpful management functions:

public class Address {
    private Address next;
    private int houseNumber;

    public Address ( houseNumber, ... ) {
       this.next = null;
       ...
    }
    public Address getNext () {
       return this.next;
    }
    public void setNext ( Address a ) {
       this.next = a;
    }
    public void setHouseNumber ( int hn ) {
    // verify format
    // ..
       this.houseNumber = hn;
    }
    public int getHouseNumber () {
       return this.houseNumber;
    }

    ....
}

public class AddressList {
    private Address head;
    private int count;
    
    public AddressList () {
        this.head  = null;
        this.count = 0;
    }

    public Address getNext ( Address ) {
        if ( null == Address )
           return this.head;
        return Address.getNext ();
    }
    public Address Add ( int houseNumber, ... ) {
        Address a = new Address ( houseNumber, ... );
        a.setNext ( this.head );
        this.head = a;
        this.count++;
        return a;
    }
}
public class Test {
    public static void main () {
        AddressList list = new AddressList;
        list.Add ( 21, ... );
        list.Add ( 22, ... );
        list.Add ( 23, ... );
        list.Add ( 24, ... );

        // iterate list
        Address iter = null;
        while ( null != ( iter = list.getNext ( iter ) ) ) {
            iter.setHouseNumber ( ... );
            ...
        }
    }
}
 

Or something like that.

Depending on whether you want the list to be traversable both ways and random node deletions, you might need a prev reference as well.

Share this post


Link to post
Share on other sites

Posted

A linked list can be implemented in a generic or adhoc manner. There's no rule stating that all linked list implementations must be generic.

Don't Repeat YourselfSeparation of Concerns. An Address should know about Address-specific details, not how you want to store it. What's a "next" address for an Address? The next real address on the street? The next possible address? The next address in your database? How is an Address supposed to know about any of that? The "Next" member doesn't even have a well-defined meaning in this context.

Share this post


Link to post
Share on other sites

Posted

I thought it would be good to use a linked list on this one rather than an array.

 

Now that we've answered your question about linked lists in Java...

 

Most languages have standard libraries that implement lists for you. You don't have to reinvent the wheel every time. The Java API provides you with a lot of tools, so keep that documentation close.

 
ArrayList<Address> addresses = new ArrayList<Address>();
 
Scanner in = new Scanner(System.in);
for(int i = 0; i < 10; i++)
{
    System.out.println("Please enter street number: ");
    int houseNum = in.nextInt();
    System.out.println("Please input street name: ");
    String street = in.nextLine();
    System.out.println("Please input city: ");
    String city = in.nextLine();
    System.out.println("Please input state: ");
    String state = in.nextLine();
    System.out.println("Please enter street zip: ");
    int zip = in.nextInt();
 
    Address a = new Address(houseNum, street, zip, city, state);
    addresses.add(a);
}
 
1 person likes this

Share this post


Link to post
Share on other sites

Posted

<a data-ipb="nomediaparse" data-cke-saved-href="http://en.wikipedia.org/wiki/Don" href="http://en.wikipedia.org/wiki/Don" t_repeat_yourself"="">Don't Repeat Yourself,  Separation of Concerns.

All very good practices, and ones I adhere to myself generally. But I'm also flexible and don't take them to the extreme.

 

An Address should know about Address-specific details, not how you want to store it.

In the strictest OOP sense, yes, but I don't see it as a problem for a quick project. Especially for someone who's new to the whole concept. Besides, we're only talking about two accessor functions and a single private variable, we're not subverting the whole class and creating an ambiguous mess. But if he wants to, I'm sure he can create a generic linked list once he fully understands the concepts.

 

What's a "next" address for an Address? The next real address on the street? The next possible address? The next address in your database? How is an Address supposed to know about any of that? The "Next" member doesn't even have a well-defined meaning in this context.

It's quite obvious to anyone who knows what a linked list is what the code is doing. And a couple of comments can dispel any possible confusion. If someone wants to be an OOP purist, sure, you could argue against the practise, but I'm not that rigid or zealous myself.

Share this post


Link to post
Share on other sites

Posted

In the strictest OOP sense, yes, but I don't see it as a problem for a quick project. Especially for someone who's new to the whole concept. Besides, we're only talking about two accessor functions and a single private variable, we're not subverting the whole class and creating an ambiguous mess. But if he wants to, I'm sure he can create a generic linked list once he fully understands the concepts.

It's not an extreme or zealous position to say one shouldn't violate sound design principles without good reason. And here there's really no good reason to do it. The code won't become massively more complicated or confusing because of it, granted, but it's still not the best thing to do.

 

As for the "he's new to it" argument, that weighs more in favor of keeping the list implementation separate IMO; it's much easier to grasp a concept when you can reason about it in isolation, and the idea of a linked list that we can use to hold addresses is much easier to understand than that of an address that also happens to be a linked list node.

2 people like this

Share this post


Link to post
Share on other sites

Posted

It's not an extreme or zealous position to say one shouldn't violate sound design principles without good reason. And here there's really no good reason to do it. The code won't become massively more complicated or confusing because of it, granted, but it's still not the best thing to do.

 

As for the "he's new to it" argument, that weighs more in favor of keeping the list implementation separate IMO; it's much easier to grasp a concept when you can reason about it in isolation, and the idea of a linked list that we can use to hold addresses is much easier to understand than that of an address that also happens to be a linked list node.

You've convinced me with your well articulated response. Perhaps it is teaching a bad practise. hopefully the OP will see what you've written and adopt it.
1 person likes this

Share this post


Link to post
Share on other sites

Posted

If you want a good reason to do so, then read up on intrusive linked list (which it was was originally proposed). Intrusive linked lists have the downside of worse encapsulation, but the opportunity for better optimisation (in certain languages). For example in C you may define a singly linked list like so (to store arbitrary data):

struct ListData {
    int i;
};
 
struct LinkedList {
    LinkedList* next;
    void* data;
};

 

So to perform this allocation you will need to perform 2 mallocs, one for the data and one for the List node.

 

Now by moving the data inside the node you can reduce the number of mallocs per node to 1. If malloc is expensive and many nodes are being allocated this could have a decent performance impact. Also the data and next pointer are close together in memory so performing operations on the contained data and then moving to the next node will be less likely to cause a cash miss - again better performance.

 

struct LinkedList {
    LinkedList* next;
    int i;
};

 

C++ in general can do this better through the use of templates. If you want to know more I would read up on the boost docs, as they explain the many differences quite well.

You tend to find that intrusive containers are used a fair amount in embedded programming due to the constrained memory requirements. But in general intrusive containers will be the wrong choice. In general a linked list will be the wrong choice. If you prefer any container it should be a std::deque in C++ which is down to its implementation.

2 people like this

Share this post


Link to post
Share on other sites

Posted

That's interesting and certainly a good reason for doing it that way. While I do mostly employ my own generic container implementations, I have on occasion used adhoc, or intrusive linked lists as you called it, sometimes perhaps for the wrong reasons (speed of implementation). In C it definitely has a speed advantage because of the number of mallocs involved. Perhaps that's an over-optimisation on non-critical code or in resource abundant environments, but low memory and speed critical areas do benefit from that.

Share this post


Link to post
Share on other sites

Posted

Well now I have a linked list that works, sort of. My problem is when I am taking an integer input, it somehow has a different value than what I put in. For example:

Enter your house number:

Input: 519

Output: 551

 

What could cause number to add to it, when there are no other methods that modify the variable houseNumber? And I hope you don't ask for my code, as it looks like a three year old could write with more organization!

		System.out.println("Enter your house number:");
		int houseNum = in1.nextInt();
		System.out.println("Enter your street name:?");
		String street = in1.nextLine();
		System.out.println("Enter your city:");
		String city = in1.nextLine();
		System.out.println("Enter your state abrreviation:");
		String state = in1.nextLine();
		System.out.println("Enter your zip code:");
		int zip = in1.nextInt();


.........
			while(null != (iter = addressBook.getNext(iter))){
				System.out.println(iter.HouseNum()+' '+iter.Street());
				System.out.println(iter.City()+ ", "+iter.State()+' '+iter.ZipCode());		
			}

Share this post


Link to post
Share on other sites

Posted

 

Well now I have a linked list that works, sort of. My problem is when I am taking an integer input, it somehow has a different value than what I put in. For example:

Enter your house number:

Input: 519

Output: 551

 

What could cause number to add to it, when there are no other methods that modify the variable houseNumber? And I hope you don't ask for my code, as it looks like a three year old could write with more organization!

I suspect this has to do with:

 iter.HouseNum()+' '

This is basically equivalent to:

iter.HouseNum() + (int)' '

Which is

iter.HouseNum() + 32

Which, as you may guess, is just another integer, and not the string concatenation you thought you were doing.

 

Just use " " instead of ' '.

Share this post


Link to post
Share on other sites

Posted

I suspect this has to do with:

 iter.HouseNum()+' '

The sum of an integer and a character is the sum of the integer and the integral value of the character according to the ASCII table.

 

Just use " " instead of ' '.

Thank you!!

Share this post


Link to post
Share on other sites

Posted

I finally finished the assignment, thank you for all the help! I really appreciate it, I've been behind for a while with the death in my family as well as my new baby I expect this week! I'd buy you all beers over the internet if I could.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.