In this tutorial, we are going to learn about Linked List Data Structure in Java.

Linked List

• A linked list (One-way list) is a linear collection of data elements, called nodes, where the linear order is given by means of pointers.
• Each node is divided into two parts.
• First part contains the information of the element.
• Second part contains the address of the next node in the list.
• A singly linked list is a concrete data structure consisting of a sequence of nodes.

• Each node stores

  • element
  • link to the next node
    

Key Points of Linked list

• Linear collection of nodes.
• Connected by pointer links.
• Accessed via a pointer to the first node of the list
• Link pointer in the last node is set to null to mark the list’s end.
• Linked list contains a List Pointer Variable called START or NAME, which contains the address of the first node.

Why Linked List?

Arrays: pluses and minuses

• Fast element access.
• Impossible to resize.

Need of Linked List

• Many applications require resizing!
• Required size not always immediately available.

Use a linked list instead of an array when

• You have an unpredictable number of data elements
• You want to insert and delete quickly.

Memory Representation

• Linked lists are maintained in memory using linear arrays or Parallel arrays.
• Multiple lists in memory.
• INFO part of a node may be a record with multiple data items.
• Records in memory using Linked lists.

Types of Linked Lists

1. Singly linked list: Begins with a pointer to the first node.

   • Terminates with a null pointer.
   • Only traversed in one direction.
2. Circular, singly linked: Pointer in the last node points back to the first node.

3. Doubly linked list: Two “start pointers” – first element and last element.

   • Each node has a forward pointer and a backward pointer.
   • Allows traversals both forwards and backwards.
4. Circular, doubly linked list: Forward pointer of the last node points to the first node and backward pointer of the first node points to the last node.