P6: Linked Lists and Problem Solving

1. Objective

The goal of this assignment is to understand the concept of Linked Lists. You will write code that (1) uses the functionality of given LinkedList code, and (2) implements functionality inside the LinkedList class.

We will use LinkedLists to store and process user data from social networking applications. To emphasize problem solving, you will also be required to determine by yourself what helper methods to add inside certain classes to implement the required methods for a given class.

The application involves a social networking site similar to say, LinkedIn. Each user has an account. A user may have zero or more connections. We will maintain the connections of each user as a separate Linked List. In this application, a connection is symmetric; if user X becomes connected to user Y, then Y is also connected to X. It should be possible to find the users that are connected directly to a user or via a common connection. Note that a connection is not reflexive: X can never be considered to be directly or indirectly connected to X.

2. Tasks

This application needs three classes:

1. Account: You will implement this class.
2. Node: You can download this class here. It is similar to the Node class you saw in the lecture. The difference is that it stores objects of type Account rather than Object. You should not change this class.
3. LinkedList: You can download this class here. This is the same class that you saw in the lecture and recitation, but has an extra method called get(int index). You are free to add new methods but do not change the existing methods.

Implement the Account class as follows:

List of attributes in Account:

1. private String username; // stores the username of the user
2. private String name; // stores the name of the user
3. private LinkedList connections; // stores the connections of the user

Account Constructor:

• public Account(String username, String name): The constructor sets the username and name. There are no connections at this point but the connections instance variable must be appropriately initialized to enable the addition of connections later.

List of Methods in Account:

1. public String getUserName(): Returns the username.

2. public String getName(): Returns the name.

3. public LinkedList getDirectConnections(): Returns the connections instance variable. It stores user accounts that are directly connected to this user. The order of connections in the returned LinkedList does not matter.

4. public String toString(): For example, if the username is "ghosh" and name is "Sudipto Ghosh", then the method returns:
   Username: ghosh, Name: Sudipto Ghosh

5. public boolean equals(Object other): Returns true if the username of other is the same as username of this object. False otherwise.

6. public int getNumberOfDirectConnections(): returns the number of direct connections of this user.

7. public void addConnection(Account other): As long as the other account isn't already in the connections list, add the other account. Note that one cannot add oneself as a connection. Moreover, recall that a connection is symmetric.

8. public LinkedList getCommonConnections(Account other): Returns a linked list of accounts of users that are connected with both this and the other account. If there are no common connections, this method should return an empty LinkedList (i.e., not a null one). The order of connections in the returned LinkedList does not matter.

9. public int getNumberOfSecondLevelConnections(): Returns the number of accounts that are indirectly connected to this user via a common connection but not directly. That is, if X is connected to Y, and Y is connected to Z, then the connection between X and Z is a second level connection.

   However, if X is connected to Y and Z, and Y is connected to Z, we will not count the connection from X to Z as a second-level connection.

   Moreover, we only count unique accounts. That is, if A is connected to B and C, and B and C are both connected to D, then you should count the second-level connection between A and D only once.

   Finally, remember that A cannot be connected to itself directly or indirectly.

You may find it helpful to include helper methods in the LinkedList class in order to implement the above methods in the Account class. However, that is entirely your choice. We will only test the methods in the Account class. Hint: Look up what methods are available in the ArrayList class (e.g., contains, indexOf, etc) that are not available in the given LinkedList class, and determine which one(s) will make it easier to implement Account.

3. Preliminary and Final Testing

As always, remember that we will not test your main method. The methods you implement will be tested directly by the test server. Ideally, you should create your own main methods, perhaps one in each class, to test each class separately and together. Preliminary testing will cover some methods and a limited set of situations in these methods. Final testing may use other data.

Here is a sample barebones main method for the Account class. It does not test all the methods, nor does it test for various situations.

    public static void main(String[] args){
        Account alice = new Account("alice", "Alice A");
        Account bob = new Account("bob", "Bob B");
        Account cody = new Account("cody", "Cody C");
        Account david = new Account("david", "David D");
        alice.addConnection(bob);
        bob.addConnection(cody);
        cody.addConnection(david);
        cody.addConnection(alice);
        System.out.println(alice);
        System.out.println(alice.getUserName());
        System.out.println(alice.getName());
        System.out.println(alice.getDirectConnections());
	System.out.println(alice.getCommonConnections(cody));
    }

4. Submission

Create a single jar file called P6.jar from the two Java files (Account.java and LinkedList.java) using the instructions provided here. Do not add other files (e.g., class files). You should not add Node.java because it is supposed to remain unchanged.

Submit the P6.jar file via the online checkin system.