Java single LinkedList add with O(1) complexity

Question

I'm trying to understand LinkedLists(Single LinkedList to be precise).

I heard/read that delete and add operation will be performed with O(1) complexity and I'm still not getting how to implement with O(1) complexity for these two operation. Below is my implementation in java(NOTE: I don't know c, c++ coding, So I recently started understanding data structures).

public class Node
{
    private Integer data    = null;
    private Node    next    = null;
    private int     size    = 0;

    public Node()
    {

    }

    private Node(Integer data)
    {
        this.data = data;
    }

    public boolean add(Integer data)
    {
        if (null == data) return false;
        if (null == this.data)
        {
            this.data = data;
        }
        else
        {
            if (null == this.next)
            {
                this.next = new Node(data);
            }
            else
            {
                this.next.add(data);
            }
        }
        size += 1;
        return true;
    }

    public Integer getDataAt(int index)
    {
        if (index == 0)
        {
            return this.data;
        }
        else
        {
            return this.next.getDataAt(index - 1);
        }
    }

    public int getSize()
    {
        return size;
    }
}

Please suggest me to edit as of now add(data) to make it O(1) complexity.

If you had a variable referencing the end of your linked list, then you could add something straight onto it without having to iterate through the list. — khelwood
– khelwood, Commented May 25, 2017 at 11:32
Addition to the end or in the beginning is always O(1) since you iterate nothing (if you have reference to the tail), remove operation should be O(n) in default linked list since at most you will need to travers from the end to the beginning. You can always use binary search to remove element (still not O(1) and in need of use double linked list) or use dictionary for it (however it is not true linked list) — MaLiN2223
– MaLiN2223, Commented May 25, 2017 at 11:32
@MaLiN2223 You cannot use binary search on linked list. Binary search relies on jumping from index x to index x / 2. In case of linked list, you cannot just "jump", you have to iterate through x / 2 elements. — Jaroslaw Pawlak
– Jaroslaw Pawlak, Commented May 25, 2017 at 11:38
@JaroslawPawlak what do you mean by "I cannot" ? Of course I can, does anything prevents me from iterating over list even if it is x/2 elements? — MaLiN2223
– MaLiN2223, Commented May 25, 2017 at 11:39
@MaLiN2223 If you iterate over your entire list, it's not really a binary search anymore. Binary search has time complexity O(logn), while your pseudo binary search would have time complexity O(n). — Jaroslaw Pawlak
– Jaroslaw Pawlak, Commented May 26, 2017 at 9:29

Neeraj Jain · Accepted Answer · 2017-05-25 12:48:11Z

5

Only Adding and Removing operation in LinkedList is O(1) but traversing to the node you want to remove or add is an O(N) operation

You can achieve the O(1) complexity if you keep the reference to your last added element so you can put add new Node to the last traversed element's next Node.

edited May 25, 2017 at 12:48

answered May 25, 2017 at 11:35

Neeraj Jain

7,7308 gold badges36 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

MaLiN2223 Over a year ago

Also, O(1) complexity can be achieved when you add elements in the beginning.

steffen Over a year ago

@MaLiN2223 or at the end.

gati sahu · Accepted Answer · 2017-05-25 13:30:14Z

1

In linkedList if you have head and tail pointer to point first and last of node linkedlist then in constant time you can add and remove in first or last position of the node.If you want to delete an element you have to find that element and in worst case that element will be in last .In doubly linkedlist you can start from start and end so you have to traverse till so in worst case it will be O(n).

answered May 25, 2017 at 13:30

gati sahu

2,6512 gold badges12 silver badges16 bronze badges

Comments

Suryaprakash Pisay · Accepted Answer · 2017-05-26 08:33:57Z

Thank you for all your support, as a NOOB in data structure I want to understand how ds workds rather than copy pasting from someone's else implementation.

Neeraj Jain & Gati Sahu's explanations/answer helped me to achieve what I'm looking for add(data) in LinkedList with O(1) complexity.

So what I did is "Segregate Plain Node class and create LinkedList class with operations.

class Node
{
    private Integer data    = null;
    private Node    next    = null;

    public Node(Integer data)
    {
        super();
        this.data = data;
    }

    public Integer getData()
    {
        return data;
    }

    public Node getNext()
    {
        return next;
    }

    public void setData(Integer data)
    {
        this.data = data;
    }

    public void setNext(Node next)
    {
        this.next = next;
    }

}

public class LinkedList
{
    Node    head;
    Node    end;

    public Node getHead()
    {
        return head;
    }

    public boolean add(Integer data)
    {
        if (null == head)
        {
            head = new Node(data);
            end = head;
        }
        else
        {
            addAtEnd(data);
        }
        return true;
    }

    public void addAtEnd(Integer data)
    {
        end.setNext(new Node(data));
        end = end.getNext();
    }

    public void addAtFirst(Integer data)
    {
        Node tmpNode = head;
        head = new Node(data);
        head.setNext(tmpNode);
    }
}

Collectives™ on Stack Overflow

Java single LinkedList add with O(1) complexity

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related