10

By definition Linked List is a list that each element of it refers to the next element (and previous element if we are talkin about double linked list.) http://en.wikipedia.org/wiki/Linked_list

However, in Java LinkedList is implementing List, Queue, Deque and more. http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html

You can not find a method in LinkedList that gives you next or previous object in the list, the best you can do is to get an Iterator and get objects. My question is why Java has called this data structure LinkedList, while it is not truly a linked list? A linked list can be implemented in Java like this:

Public class MyLinkedList{ public int value; public MyLinkedList next; }
Improve this question

7 Answers 7

Reset to default
10

You can not find a method in LinkedList that gives you next or previous object in the list

No, and that's entirely appropriate. The idea of "next item in a list" doesn't make sense on a list. It makes perfect sense for a node within a list, but that's not something which is exposed by the Java API. It's present internally, of course - just not exposed. If you want to iterate over the list, you use an iterator. You can still add at the start or end, remove from the start or end, and add/remove from the iterator.

While you certainly can conflate the concepts of "node" and "list" as your suggested sample code does, I don't think it's generally a good idea.

To put it another way: what are you trying to achieve that's causing you problems? I believe you should be able to do what you want using the public API - you may just not have noticed it all.

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

1 Comment

You can get a next or previous item in the list when using the list iterator.
7

My question is why Java has called this data structure LinkedList, while it is not truly a linked list?

Because the implementation of it is a linked list. From the documentation:

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

LinkedList is a List implemented via a linked-list, ArrayList is a List implemented using an array, etc. Which one you choose can matter in terms of runtime characteristics. For instance, from the LinkedList docs:

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

So you know, for instance, that next on the Iterator you get from iterator or listIterator will be quite efficient, but that get by index will involve traversal.

Improve this answer

3 Comments

Oh, so you mean the implementation of LinkedList is a linked list, but it is not providing linked list functionality when you use LinkeList?
@sheidaei: I'd argue that it does, via Iterator and ListIterator, and the fact that you know (from the docs) that the underlying structure implements those using a doubly-linked list and thus next and previous will be quite efficient.
Different algorithms requiring storing linked list nodes in a cache so that they can be easily deleted or updated. For e.g. LRU cache algorithms. Java does not expose the concept of Linked list node to the client. This prevents the client from efficiently implementing those algorithms. Perhaps asked differently, how would one go about implementing algorithms requiring caching of linked list nodes to support o(1) inserts/deletes before/after that doubly linked node
4

Whether a collection is a linked list or an array list is not about its contract, but about its implementation. LinkedList is indeed a linked list by implementation, and a java.util.List by contract.

Where it shows is not its API, but its space/time complexity characteristics, which anyone familiar with a linked list can easily anticipate.

For reference, this is the actual implementation of a LinkedList node, quite a good match to your expectation:

957 private static class Node<E> {
958 E item;
959 Node<E> next;
960 Node<E> prev;
962 Node(Node<E> prev, E element, Node<E> next) {
963 this.item = element;
964 this.next = next;
965 this.prev = prev;
966 }
967 }

Improve this answer

Comments

2

As I read through your question, I got a feeling that you didn't distinguish between the concept of linked list and the implementations of linked list well.

Your sample code demonstrated the concept of linked list very well, but that doesn't mean it's the only way or the best way to implement the linked list. I believe that you can do any operations that a standard linked list entails using the built-in LinkedList class, although you might see an unfamiliar set of APIs as you see in your data structure class or textbook.

So basically, it is a linked list as long as you can achieve insert operation in O(1) time, delete operation in O(1) time, search operation in O(n) time, etc., in contrast to the time complexity of other data structures such as array.

The built-in LinkedList didn't provide the next operation directly but through its iterator. It was just a design decision of the Java language because you might benefit from the Iterator pattern.

And Java is a typical object-oriented language, one of the main characteristics of which is Abstraction.

Improve this answer

Comments

1

In addition to the correct answers by the others, if the underlying implementation of the interface is a Linked List, the implementing object will have a method to get the next item in the list. That method is just not exposed as part of the contract.

The fact that the implementation is a linked list impacts the Big-O performance of the various methods of the List contract.

Improve this answer

Comments

0

However, in Java LinkedList is implementing List, Queue, Deque and more.

According to the API, LinkedList implements those interfaces so it can be used any of those structures.

Improve this answer

Comments

0

So I don't know where @Marko was reading that implementation from but the one in the 1.8 jdk is vastly different.

For one, the very first variable declared is:

 transient int size = 0;

That value is incremented whenever a node is added to the list. This means there is an inherent limit of Integer.MAX_VALUE (2147483647) nodes in the list. In the modern world, that number isn't as big as it looks. The problem so much isn't that we don't have a real linked list (they're trivial to create), but with all the 3rd party libraries, they will most likely not be accounting for this and then the whole library gets chucked.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.