CODEWITHSUNDEEP
javalinked-listadditiondoubly-linked-list
shuizhuyu1
shuizhuyu1

Reputation: 33

LinkedList (built from scratch) add() not working

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

Upvotes: 3

Views: 96

Answers (4)

Abhishek Soti
Abhishek Soti

Reputation: 64

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

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

Upvotes: 0

Thiyanesh
Thiyanesh

Reputation: 2360

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));
        }
    }

Upvotes: 2

Mohd Murad
Mohd Murad

Reputation: 35

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

Upvotes: 0

Andrew Merrill
Andrew Merrill

Reputation: 1742

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?

Upvotes: 0

Related Questions