LinkedList (built from scratch) add() not working

user_14628300 0
Viewed 86

I'm working on a class assignment where I must build a singly linkedlist class from scratch. My problem here is that my add() method isn't quite working when I iterate through a series of items and add them to a linkedlist. More specifically, 1) it is duplicating the first one in a series, and 2) it is not adding the last one in a series. What is wrong with my add() method in the ManualLinkedList class?

public class test {
    static class ManualLinkedList<T> {
        private static class Node<T> {
            T item;
            Node<T> next;
            Node<T> prev;

            public T getItem() {
                    return item;
                }
            public ManualLinkedList.Node<T> getNext() {
                    return next;
                }

            Node(Node<T> prev, T element, Node<T> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

        Node<T> head;
        Node<T> tail;
        int size = 0;

        public void add(T t) {
            final Node<T> l = tail;
            final Node<T> newNode = new Node<>(l, t, null);
            tail = newNode;
            if (l == null) {
                head = newNode;
            }
            else {
                l.next = newNode;
            }
            size++;
        }

        public int size() { return size; }

        public T getContentFromPosition(int position) {
            Node<T> np = head;
            T result = head.getItem();

            if (position == size) {
                result = tail.getItem();
            }
            for (int i = 1; i < size; i++) {
                if (i == position) {
                    result = np.getItem();
                }
                np = np.getNext();
            }
            return result;
        }
    } //end ManualLinkedList class


    public static void main(String[] args) {
        ManualLinkedList<Integer> test = new ManualLinkedList<>();
        test.add(1);
        test.add(2);
        test.add(3);
        test.add(4);
        test.add(5);
        test.add(6);
        test.add(7);
        test.add(8);

        for (int i =0; i < test.size; i++){
            System.out.println(test.getContentFromPosition(i));
        }
    }
}

Expected Output:

1
2
3
4
5
6
7
8

Actual Output:

1
1  // notice the duplicate first item
2
3
4
5
6
7  // notice the missing 8, or the last input
doubly-linked-list add linked-list java
4 Answers

Primary Issues

  1. index is used as 0..size-1 during invocation
  2. for loop in getContentFromPosition should be from 0..size-1
  3. The usage of size == position is irrelevant in getContentFromPosition

Code

        public T getContentFromPosition(int position) {
            if (position >= size) {
                return null;
            }
            Node<T> np = head;
            T result = head.getItem();
            if (position == size - 1) {
                result = tail.getItem();
            }
            for (int i = 0; i < size; i++) {
                if (i == position) {
                    result = np.getItem();
                    break;
                }
                np = np.next;
            }
            return result;
        }
    } //end ManualLinkedList class


    public static void main(String[] args) {
        ManualLinkedList<Integer> test = new ManualLinkedList<>();
        test.add(1);
        test.add(2);
        test.add(3);
        test.add(4);
        test.add(5);
        test.add(6);
        test.add(7);
        test.add(8);

        for (int i = 0; i < test.size; i++){
            System.out.println(test.getContentFromPosition(i));
        }
    }
user_151024590

Your add function is actually fine.

However, your getContentFromPosition function is almost right, but needs a little work. You should decide whether the positions in your list count from 0 or from 1. For example, if there are 3 elements in a list, are they are positions 0, 1, 2 or positions 1, 2, 3?

When you are using the getContentFromPosition function from main, you are assuming that positions count from 0, but in writing the function, it looks like you were assuming that they count from 1.

If you modify the getContentFromPosition to count from 0, then you can get rid of the special case checking for position==size, and you would then start the loop at 0, not 1. Also, for efficiency, why not return the result when you find it rather than let the loop continue to run?

user_15469890

you need to initialized int size=1 instead of 0

and in the main method for loop change to int i=1 instead of 0

user_138910970

in getContentFromPosition method, your for loop should start from 0. Rest is fine.

for (int i = 0; i < size; i++)

user_66277470
Related