Linked Lists

Linked Lists Versus Arrays

• Arrays are fixed size
• An array orders its items physically and needs to shift its data after we insert or remove an item
• For arrays the entire array is stored in one block of memory
• Array access with indexes is implemented using the fast address arithmetic
• For fixed size arrays that are larger than 8K the virtual memory will take care of the wasted part
• An array allocates memory for all its elements lumped together as one block of memory, but linked list allocates memory for each element separately

Pointer Allocation in C++

 //Static allocation, compiler allocation, stack int * p; //Dynamic allocation, runtime allocation, heap int* p = new int; 

How to allocate an array

 int* myArray = new int[50]; //myArray[0] *myArray; //myArray[1] *(myArray + 1); //Deleting delete [] myArray; 

More Links

• Linked List Basics
• Root path
• Linked List Problems
• How pointers and memory work
• All the basic features of the C Programming language

Each linked list starts with a head pointer that is an ordinary local variable placed on the stack but the list nodes are allocated on the heap