This is a pretty simple question but I’m new to java.
The linked list found in java.util.LinkedList.
I saw elsewhere that Java does not use pointers…
When I create a new list and add new elements to it, does the list contain references to the data and to the next/previous elements or does it also contain the object itself.
3
In Java you have primitives (int, long, etc.) and objects. Objects are references (pointers) to complex data.
Java always passes values; so within your list you will have actual values of what you put in. BUT: Since objects are references to data, the values passed will be the references, not the data itself.
Pragmatic result: You put object A in a list and change its data somewhere in your code. Object A will still be in your list (you didn’t change A but its data) but the A in your list will reflect the changes you’ve made somewhere else.
Car a = new Car();
List myList = new LinkedList();
myList.add(a);
a.driveHome();
Car carFromList = myList.getFirst();
carFromList.isDrivenHome(); // true
5
You can check out the OpenJDK LinkedList implementation on GrepCode. The LinkedList class itself contains a reference to an Entry named header, which contains references to two more Entry objects for the next and previous elements in the list.
1
To answer specifically: note that java.util.LinkedList defines a doubly-linked list.
The list has two member variables first and last that reference (“point at”) the first and last nodes. List nodes are of type Entry<T>, where T is the type of the objects you are inserting.
Each list node or Entry thus contains:
T data : the actual item (object) inserted
Entry<T> next : a reference to (“pointing at”) the next node (null if last)
Entry<T> previous : a reference to (“pointing at”) the previous node (null if first)
For example, list (A,B,C,D) is represented as follows:
/ -> / -> / -> /
| A | | B | | C | | D |
/ <- / <- / <- /
^ ^
first last
- LinkedList uses index to store elements
- Elements are point(linked) to each other
There are 3 types of linked list
1.singly linked list = each node point the next node. (x)—>(y)—>(z)—>nothing
2.doubly linked list = each node point to next and previous node . (x)<–>(y)<–>(z)
3.circularly linked list. = each node point to next node (like singly-linked lists) last node and fist node linked
(x)—>(y)—>(z)—>(x)
4