Data Structures in Java - Linked List

Linked List

Linked List is a dynamic data structure (data can grow and shrink on demand). Compared to arrays, which are static structures, linked list is a linear data structure (form sequence) which supports insertion and deletion of elements easily.

Each element (Node) is composed of two items, data and reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. One disadvantage of linked list against array is that it does not allow direct access to the individual elements, also it uses more memory compared to array.

There are two types of Linked List.

1. Singly Linked List - Each node in the chain has single link, Good for forward traversal

2. Doubly Linked List - Each node in the chain has two link, Good for forward and backward traversal within the chain

Basic Operations

Building Linked List

To build a linked list that contains the items “to”, “be” and “and”, we create Node for each item, set the item field in each of the node to the desired value, and the set the next field to the build the linked list.

Node first = new Node();
first.item = "to";
first.next = second;

Node second = new Node();
second.item = "be";
second.next = third;

Node third = new Node();
third.item = "or"

Inserting at the Beginning

Node oldFirst = head;
head = new Node();
head.item = "not";
head.next = oldFirst;

Traversal

Node tmp = head;
while (tmp != null) tmp = tmp.next;

Example

Reference

• Linked Lists