by BehindJava

What is Linked List in Data Structures

Home » datastructures » What is Linked List in Data Structures

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 ll
    • 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. lll
  • Multiple lists in memory. lll
  • INFO part of a node may be a record with multiple data items.
  • Records in memory using Linked lists. lll

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.