Jump to content



Photo

[Java]Linked List Implementation


  • Please log in to reply
18 replies to this topic

#1 SpeedyTheSnail

SpeedyTheSnail

    Resident Snail Herder

  • Joined: 29-June 04
  • Location: Caprica

Posted 30 April 2014 - 16:56

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!




#2 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 14
  • Joined: 26-October 05

Posted 30 April 2014 - 17:11

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.



#3 OP SpeedyTheSnail

SpeedyTheSnail

    Resident Snail Herder

  • Joined: 29-June 04
  • Location: Caprica

Posted 01 May 2014 - 06:14

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...



#4 rfirth

rfirth

    Software Engineer

  • Tech Issues Solved: 2
  • Joined: 11-September 09
  • Location: Baton Rouge, Louisiana
  • OS: Windows 8
  • Phone: Nokia Lumia 620

Posted 01 May 2014 - 06:29

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;
}


#5 virtorio

virtorio

    Neowinian Senior

  • Tech Issues Solved: 15
  • Joined: 28-April 03
  • Location: New Zealand
  • OS: OSX 10.10, Windows 8.1
  • Phone: LG G3

Posted 01 May 2014 - 06:34

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;
}


#6 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 14
  • Joined: 26-October 05

Posted 01 May 2014 - 15:10

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.



#7 OP SpeedyTheSnail

SpeedyTheSnail

    Resident Snail Herder

  • Joined: 29-June 04
  • Location: Caprica

Posted 01 May 2014 - 16:17

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



#8 simplezz

simplezz

    Neowinian Senior

  • Tech Issues Solved: 8
  • Joined: 01-February 12

Posted 01 May 2014 - 19:17

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.

#9 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 14
  • Joined: 26-October 05

Posted 01 May 2014 - 19:34

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.



#10 rfirth

rfirth

    Software Engineer

  • Tech Issues Solved: 2
  • Joined: 11-September 09
  • Location: Baton Rouge, Louisiana
  • OS: Windows 8
  • Phone: Nokia Lumia 620

Posted 01 May 2014 - 19:44

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);
}
 


#11 simplezz

simplezz

    Neowinian Senior

  • Tech Issues Solved: 8
  • Joined: 01-February 12

Posted 01 May 2014 - 19:54

<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.

#12 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 14
  • Joined: 26-October 05

Posted 01 May 2014 - 20:10

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.



#13 simplezz

simplezz

    Neowinian Senior

  • Tech Issues Solved: 8
  • Joined: 01-February 12

Posted 01 May 2014 - 20:23

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.

#14 Lant

Lant

    Neowinian Senior

  • Tech Issues Solved: 1
  • Joined: 13-April 06

Posted 01 May 2014 - 21:48

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.



#15 simplezz

simplezz

    Neowinian Senior

  • Tech Issues Solved: 8
  • Joined: 01-February 12

Posted 02 May 2014 - 15:33

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.