Creating a linked list from an arraylist

Question

My teacher wants us to create a linked list class from scratch and one part of that is writing a constructor that takes a generic arraylist and turns it into a linked list and I'm having trouble with it.

Here's the code I have so far:

public LinkedList(ArrayList<E> list)
{
    //If the list is null or initialized but empty, set head = null and size = 0.
    head = null;
    size = 0;
    if (list != null && !list.isEmpty())
    {
        //Creating a new Node manually to set the head pointer to.
        head = new Node<E>(list.get(0));
        //The current Node is for iterating through the list.
        Node<E> current = head;
        for (int i = 0; i < list.size(); i++)
        {
            //Creating a new Node that the current Node points to then making current point to the next Node.
            current.next = new Node<E>(list.get(i));
            current = current.next;
        }
        size = list.size();
    }
}

When I test it with an array of integers, say [1, 2, 3], the code will create a linked list containing [1, 1, 2] and I can't figure out why.

Answer 1

I would suggest reusing add() method if you have one:

public class LinkedList<E> {

  private int size = 0;
  private Node<E> head = null;
  private Node<E> tail = null;

  public LinkedList(List<E> list) {
    list.forEach(LinkedList::add);
  }

  public void add(E added) {
    if (head == null) {
      head = new Node<E>(added);
      tail = head;
    } else {
      tail.next = new Node<E>(added);
      tail = tail.next;
    }

    size++;
  }

  ...
}

Answer 2

I suggest the following code taken from GeeksForGeeks:

https://www.geeksforgeeks.org/java-program-to-convert-arraylist-to-linkedlist/

public static <T> List<T> convertALtoLL(List<T> aL) 
{ 
    // Create an empty LinkedList 
    List<T> lL = new LinkedList<>(); 
    
    // Iterate through the aL 
    for (T t : aL) { 
        // Add each element into the lL 
        lL.add(t); 
    }
    
    // Return the converted LinkedList 
    return lL; 
} 

Answer 3

You're creating a node for index 0 twice: once before the loop, and once in the first iteration of the loop, with i equal to 0.

I would suggest simplifying the process by iterating the array list in reverse, and prepending each new node.

To accomplish that, make sure that Node has a constructor that takes a second argument which initialises the node's next field.

Then:

public LinkedList(ArrayList<E> list)
{
    head = null;
    size = 0;
    if (list == null) return;
    size = list.size();
    for (int i = size - 1; i >= 0; i--) {
        head = new Node<E>(list.get(i), head);
    }
}

As of Java 21 you can also use reversed for this loop:

    for (E value : list.reversed()) {
        head = new Node<E>(value, head);
    }

Answer 4

Another one, if you only have head in your LinkedList class:

  public LinkedList(ArrayList<E> list)
  {
    Node<E> current = null;
    for(E value : list) {
      if (current == null) {
        head = new Node<E>(value);
        current = head;
      }
      else {
        Node<E> n = new Node<E>(value);
        current.next = n;
        current = n;
      }
    }
    size = list.size();
  }