0

In Java, I have to create a linked list from scratch (not allowed to use the LinkedList import).

I have been provided with this code as support:

public class Link<E> {
    private E e; // the element contained in this linked list
    private Link<E> next; // the next element of the linked list

    public Link(E e, Link<E> n) {
        this.e = e;
        this.next = n;
    }

    public Link(E e) {
        this.next = null;
        this.e = e;
    }

    /**
     * Method to set the element
     */
    public void setElement(E e) {
        this.e = e;
    }

    /**
     * Method to set the next linked list element
     */
    public void setNext(Link<E> e) {
        this.next = e;
    }

    /**
     * Method to get the element.
     */
    public E getElement() {
        return this.e;
    }

    /**
     * Method to get the next linked list element
     */
    public Link<E> getNext() {
        return this.next;
    }
}

With this code provided, I have to create a LinkedList with the following methods:

  1. Add objects at a specific index; addAt(data, index)

  2. Retrieve objects using the index; getAt(index i)

I have come up with the following code:

import java.util.*;

public class LinkedList<E> {

    private Link<E> head, tail;
    protected long size;

    public LinkedList() {
        super();
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void addAt(Object data, int index) {

        Link<E> temp = new Link(data);

        Link<E> current = head;

        if (data == null) {
            throw new NoSuchElementException();
        }

        if (current != null) {
            // crawl to the requested index or the last element in the list, whichever comes
            // first
            for (int i = 0; i < index && current.getNext() != null; i++) {
                current = current.getNext();
            }
        }

        // set the new node's next-node reference to this node's next-node reference
        temp.setNext(current.getNext());

        // now set this node's next-node reference to the new node
        current.setNext(temp);

    }

    public Object get(int index)
    // returns the element at the specified position in this list.
    {
        // index must be 1 or higher
        if (index < 0)
            return null;
        Link<E> current = null;
        if (head != null) {
            current = head.getNext();
            for (int i = 0; i < index; i++) {
                if (current.getNext() == null)
                    return null;

                current = current.getNext();
            }
            return current.getElement();
        }
        return current;

    }

}

However, I get a NullPointerException which I can't wrap my head around at:

temp.setNext(current.getNext()); 

Besides the NPE, I have another question: would there be a cleaner way to implement a LinkedList from scratch?

flowz0r
  • 101
  • 9
  • 1
    When you call `addAt()` on an empty list, `head` is null, so `current` will be null, which means `temp.setNext(current.getNext());` will throw NullPointerException. If it didn't, then `current.setNext(temp);` would. And if that didn't, then method would exit, but `head` and `tail` would both still be null. Re-think your logic there. – Andreas Mar 02 '20 at 23:28
  • It's also worth noting that LinkedList supports null elements so that should be taken into consideration. I don't agree with that concept but it's a part of the contract. – Jason Mar 02 '20 at 23:29
  • Also re-think how you handle `index = 0`, even if the list hadn't been empty. --- And what happens when you call `get(0)` on a non-empty list. --- When you then run into your next problem, use a **debugger** to track what is going on. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) – Andreas Mar 02 '20 at 23:31
  • @Jason This is not `java.util.LinkedList` and it doesn't implement the `java.util.List` interface, so there is no requirement to support null elements. – Andreas Mar 02 '20 at 23:32
  • @Andreas hello again :) yeah i guess that's true, op did ask if there was a cleaner way, so some info about the contract could be helpful to keep in mind. – Jason Mar 02 '20 at 23:36
  • Natural operations for a linked list with head and tail are addFirst, addLast, removeFirst, removeLast. Implement them first and test them. Only after that implement `addAt` but using only above mentioned operations. – Alexei Kaigorodov Mar 03 '20 at 16:48

0 Answers0