LINKED LIST

• Linked List

  A linear data structure where elements (nodes) are linked using pointers.
• Unlike arrays, linked lists allow dynamic memory allocation, making them more efficient for inserting and deleting elements.
• Why use linked list?

  • Dynamic Size: can grow or shrink at runtime
• Why use linked list?

  • Efficient Insertions/Deletions: no need to shift elements like in arrays
• Why use linked list?

  • Memory Utilizations: uses only the memory needed
• Node

  Fundamental building block of a linked list. Each node consist of: data, and pointer
• • Each node consist of:

  1. Data - stores the value.
  2. Pointer - stores the address of the next node
• insertAtBeginning(Node*& head, int value)

  creates a new node with the given value and makes it the new head of the list
• insertAtEndg(Node*& head, int value)

  creates a new node with the given value and adds it to the end of the list
• deleteNodeg(Node*& head, int key)


  searches for a node with the given value and removes it from the list
• displayList(Node* head)

  traverses the linked list and prints each node’s value
• LINKED LIST VS ARRAY

  A) sequentially

  B) randomly

  C) grow and shrink

  D) specified

  E) expand

  F) fixed

  G) memory

  H) ineffective

  I) different

  J) single

  K) runtime

  L) compilation

  
• TYPES OF LINKED LISTS

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List
• Singly Linked List

  each node points to the next node.
• Doubly Linked List

   each node has pointers to both next and previous node.
• Circular Linked List

  last node links back to the first node.
• ADVANTAGES

  1. Dynamic Memory Allocation - unlike arrays, linked lists can dynamically grow and shrink is needed.
  2. Efficients Insertions and Deletions - no need to shift elements like in an array.
  3. Better Memory Utilizations - only uses memory as required without wasting space.
  4. Flexible Data Structure - can easily implement stacks, queues, and graphs.
  5. Fast Insertions and Deletions in Middle -  unlike arrays, inserting or deleting an element does not require shifting.
• DISADVANTAGES

  1. Increased Memory Usage - each node requires extra memory for a pointer
  2. Slower Access Time -  elements must be accessed sequentially, unlike arrays with direct indexing.
  3. Complex Implementation - managing pointers can be tricky and may lead to memory leaks.
  4. Extra Overhead - maintaining pointers consume additional processing power.
  5. No Cache Friendly - linked lists have poor cache locality, making traversal slower than arrays.