LinkedList Tutorial: LinkedList is node-based data structure (ArrayList is array-based). It accepts duplicates and null elements also. LinkedList in Java is very easy; in fact, it is simply a Java class. Using methods we can manipulate the elements. Operations like addition, insertion and removal at any position either at the beginning, middle or at the end are a cake walk. We can assume LinkedList as a combination of stack and a double-ended queue.
The starting element is known as head and the last one in the list as tail and in between these two a chain of nodes exists. One element establishes a link with the neighbors. It is preferred by programmers as it does not keep any restriction on addition or retrieval of elements. Nodes expand when new elements are added and shrink when deleted. The last element contains a null reference as further elements do not exist to store the link.
Following is the class signature of LinkedList
public class LinkedList extends AbstractSequentialList implements List, Queue, Cloneable, Serializable
As you can obverse, the LinkedList extends AbstractSequentialList and implementse List and Queue.
Following are the constructors
- LinkedList(): Creates a LinkedlList object without any elements.
- LinkedList(Collection col): Creates a LinkedList object with the elements of collection col.
LinkedList can make use of the methods of List and Queue and apart also defines its own specific of which a few are listed below.
- void addFirst(Object obj): Adds the element obj at the beginning, before all the elements, in the linked list. The first added becomes the head.
- void addLast(Object obj): Adds the element obj at the last, after every element in the linked list. The last one becomes the tail.
- Object peek(): Returns the first element but does not delete it. That is, with peek() method, the same element can be retrieved a number of times.
- Object poll(): It works just like peek() but with a small difference. It returns and also deletes the element.
- boolean offer(Object obj): Adds the element obj at the last in the list.
- Object getFirst(): Returns the first element in the list.
- Object getLast(): Returns the last element in the list.
- Object removeFirst(): Returns and deletes the first element.
- Object removeLast(): Returns and deletes the last element.
By default, the methods of LinkedList are not synchronized (remember, Vector methods are synchronized implicitly) but a synchronized version can be obtained with Collections.synchronizedList(new LinkedList()) method as follows.
LinkedList myList = new LinkedList();
List yourList = Collections.synchronizedList(myList);
Now yourList is synchronized. Still myList is not synchronized.
LinkedList Tutorial: Refer for LinkedList Examples.
One small question, which is better to use, Vector or synchronized LinkedList?
It is better to use synchronized LinkedList. The returned list is synchronized, but still the original list is not synchronized. When non-synchronized version is required in programming, the original can be used. In the above snippet of code, in a multithreaded environment yourList can be used and non-synchronized myList can be used non-multithreaded environment. If vector is chosen, we cannot get a non-synchronized version.