Java LinkedList class

Question

In class, I've implemented my own LinkedList class with a private Node class so I've never run into this issue before. But now I'm trying to re-do a problem using Java's built-in LinkedList library and am running into trouble. (its also been a few years since I last used Java).

Lets say I had this simple skeleton. How would I pass the head Node into the function?

public static void main(String[] args)
{
    LinkedList<Integer> test = new LinkedList<Integer>();
    doSomething(test.get(0));
}


 
private static void doSomething(Node a)
{
    //stuff
}

Also could someone remind me what the difference is between these two? I know the first you're basically casting the list as a LinkedList but why do so?

List<E> test = new LinkedList<E>();
LinkedList<E> test = new LinkedList<E>();

See [What does it mean to program to an interface?](https://stackoverflow.com/q/383947/3890632) — khelwood, Jul 30 '20 at 21:48
You mention "my own LinkedList class with a private Node class". Java's LinkedList also has a hidden (private) class. You are not supposed to have access to nodes, just to the values. — f1sh, Jul 30 '20 at 22:01
In your second example, usually you declare a variable as an Interface when you want to provide interaction with different classes implementing the same interface, avoiding upcasting and downcasting everytime you do an operation with them. — Fabrizio Valencia, Jul 31 '20 at 01:53

score 1 · Answer 1 · answered Jul 30 '20 at 21:56

1

Looking at the documentation for LinkedList, there are no methods that expose the nodes of the list. In fact, LinkedList might even be implemented in a completely different way and not use nodes at all and still have all the properties and performance guarantees of a linked list. It's an implementation detail.

answered Jul 30 '20 at 21:56

Egor

39,695
10
113
130

I think the get method I have returns the node at a certain index? Also, if the function was then to add a node and I do Node a = new Node(data) this also gives me an error – Felix Jul 31 '20 at 01:34
LinkedList's get method returns an element stored in a node at that index, not the node itself. – Egor Jul 31 '20 at 03:32

rcgldr · Answer 2 · 2020-07-31T06:51:19.030

Java's native linked class has some issues. Iterators can be used to access nodes, but are limited as noted below. There is no way to move nodes within a list or from list to list, such as C++ std::list::splice.

https://en.cppreference.com/w/cpp/container/list/splice

For Java, "moving" nodes requires removing and inserting nodes, which involves deallocation for any node removed, and allocation for any node inserted.

Java's iterators can't be shallow copied. An assignment just sets another variable to point to the same iterator object. (C++ iterators don't have this issue).

Any removal or insertion of nodes from a list will invalidate all iterators to that list (except for the iterator used to do the remove or insert). (C++ iterators function as expected).

score 0 · Answer 3 · answered Jul 31 '20 at 03:56

The standard library LinkedList class uses encapsulation to avoid exposing implementation details (like how list nodes are implemented) to the user of the class (you).

There is no way you can get a reference to the internal list node, save for using advanced techniques like reflection that break encapsulation.

Instead of playing around with list nodes and pointers between them, you use the methods the LinkedList class provides to add and retrieve the list elements. For example:

LinkedList<Integer> test = new LinkedList<Integer>();
test.add(314);
test.add(879);

Integer first = test.getFirst(); // returns 314
Integer first = test.get(1); // returns 879

The benefit from encapsulation is that JVM implementors are free to change the internal implementation of LinkedList completely without fear of breaking your program.

You get the same benefit in your own program if you use the List interface instead LinkedList class by writing:

List<E> test = new LinkedList<E>();

If you do this, you are free to change test from LinkedList to ArrayList or any other list implementation at a later point with no other changes to the code, for example if the application requirements change or if you find that ArrayList gives you better performance.

Thanks Joni. Maybe I'm mixing up how I would put nodes as parameters to the methods when I was implementing my own LinkedList class but if you were using a LinkedList, wouldn't you want to pass the head or end node rather than the entire LinkedList? It would save on a lot of space. — Felix, Jul 31 '20 at 17:56
There is no difference in space usage. Object references in Java take the same amount of space no matter what object is being referenced: a reference to the entire linked list takes the same amount of space as a reference to a single list node. See also "are parameters passed by value or by reference" https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value — Joni, Jul 31 '20 at 18:02
Oh I see, thanks. Maybe I'm getting confused with C++ where parameters call the constructor which allocates the necessary memory — Felix, Jul 31 '20 at 20:15

Java LinkedList class

3 Answers3