Help making a singly linked list in Java

Question

Hi all,

This is for homework but please know that I have looked online for help (such as http://www.sethi.org/classes/class_stuff/cis435/others/notes-java/data/collections/lists/simple-linked-list.html) and my textbook but I am still having some issues.

Any help would be appreciated...

Right now I'm trying to just insert values in but nothing is working. Whether it's the first item, whether it's being added as the last one, or somewhere in between.

Node header = null;    // First element of list.
Node back  = null;    // Last element of list.

public void insert(int i, double value){ //insert value before i-th element
  Node e = new Node();
  e.num = value;
  Node curr = header;
  for(int x=0;x<i;x++) {
   if (i == 1) { //we want to insert as first thing
    if (size == 0) { //its the FIRST time we add something
     header.next = e;
     e.next = back;
     break;
    } else if (size == 1){
     e.next = header.next; //i.e. the second thing in the list
     header.next = e;
     break;
    } else {
     e.next = header.next.next; //i.e. the second thing in the list
     header.next = e;
     break;
    }
   }
   else if (x == (i-1)) {
    e.next = curr.next;
    curr.next = e;
    break;
   }
   curr = curr.next;
  }
  size = size+1;
 }

Not really sure why it isn't working.

Thanks!

Answer 1

A few suggestions:

1. implement java.util.List
2. Think about generics
3. Read this.

Start with "insert at the end" before you think about "insert at i".

Answer 2

1. In the line e.next = header.next.next what would happen if header.next points to a 'null'? Is it possible to get there?
2. What are the corner cases you have to deal with and have you taken them all into account?
3. Can you start with the simplest case first, adding either an element to the front or an element to the back? Then use those functions to implement the insert?

Answer 3

For some reason, people who are still learning to program make things far more complicated then they need to be. I did it when I was learning java, I still do it when I am just getting into a new language, and students that I have marked find new and amazing ways to do it. You have more going on in your insert then there needs to be, for example, a method that inserts a value at a specific index should not check if it's the first item to be inserted (not saying it shouldn't check bounds). Here is the pseudo code of what I would do.

insert(index, value)
    if index>size
        throw null pointer
    traverse to index -1 //lets call this nodeI
    create newnode and set value
    set newnode.next to nodeI.next
    set nodeI.next to newnode
    increase size.

Couple of handy hints for you, you should have a function to get an element from the link list, something that returns a node? public node elementAt(int index) for example? use that to traverse the linked list. If you want to append to the Linked list, try this

append(value)
    insert(size-1,value)

and if you want to insert at the beginning? same idea

insert(value)
    insert(0,value)