What is Linked List in Data Structures
In this tutorial, we are going to learn about Linked List Data Structure in Java.
- 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
- 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.
Arrays: pluses and minuses
- Fast element access.
- Impossible to resize.
- Many applications require resizing!
- Required size not always immediately available.
- You have an unpredictable number of data elements
- You want to insert and delete quickly.
- 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.
Singly linked list: Begins with a pointer to the first node.
- Terminates with a null pointer.
- Only traversed in one direction.
- Circular, singly linked: Pointer in the last node points back to the first node.
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.
- 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.