LinkedList

  1. The underlying data structure is double linked list.
  2. Insertion order is preserved.
  3. Duplicates are allowed.
  4. Heterogeneous objects are allowed.
  5. Null insertion is possible.
  6. LinkedList implements Serializable and Cloneable interfaces but not RandomAccess interface.
  7. LinkedList is best choice if our frequent operation is insertion and deletion in the middle.
  8. LinkedList is worst choice if our frequent operation is retrieval operation.
  9. Usually we can use LinkedList to implement stacks & queue to provide support for this requirement LinkedList class defines following specific methods.
  10. In retrieval, 1st element takes 1sec to find, 2nd element takes 2sec to find. Hence nth element takes n sec. So time complexity is O(n)

A double linkedList whose node contains three fields, 1st field either points to the start or address of the previous node, 2nd field contain the data or 3rd field either contain the next node address or points to the end (null).

  LinkedList node

Previous node address or
address point
Data Next node address
or null

LinkedList list points to the 1st element and it has the address of the second node where second node will contain the address of previous node, data and address of next node.

Methods of LinkedList

void addFirst();

void addLast();

Object getFirst();

Object getLast();

Object removeFirst();

Object removeLast();

Constructors of LinkedList

LinkedList list = new LinkedList();

Creates an empty LinkedList object.

LinkedList list= new LinkedList(Collection c);

Creates an equivalent linked list object for given collection.

Examples

package List;

import java.util.LinkedList;

public class LinkedListDemo {

	public static void main(String[] args) {
		LinkedList l1 = new LinkedList();
		l1.add("durga");
		l1.add(30);
		l1.add(null);
		l1.add("durga");
		System.out.println(l1); // [durga, 30, null, durga]
		l1.set(0, "software");
		System.out.println(l1); // [software, 30, null, durga]
		l1.add(0, "venky");
		l1.addFirst("ccc");
		System.out.println(l1); // [ccc, venky, software, 30, null, durga]
	}

}

235 total views, 1 views today