Skip to content

Linked List

  • Linear DS
  • Non-contagious
  • Pointers

Why ?

  • dynamic size
  • inserting / deleting -> less expensive

Drawbacks

  • Random Access not allowed
  • extra memory for pointer
  • not cache friendly -> no locallity of refernce -> non contagious

Representation

  • Data + next pointer -> node
  • Linked List -> Meta data + Start
class Node { 
public: 
    int data; 
    Node* next; 
};

Traversal

void printList(Node* n) 
{ 
    while (n != NULL) { 
        cout << n->data << " "; 
        n = n->next; 
    } 
}