Linear Data Structure :
Linked List
Problem With Array
• Fixed Length (Occupy a Block of memory)
• To expand an Array
– create a new array, longer in size and copy
the contents of the old array into the new
array
• Insertion or Deletion algorithms (already
studied)
3
Solution
• Attach a pointer to each item in
the array, which points to the next
item
–This is a linked list
–A data item plus its pointer is
called a node
4
Linked List node
node
A
data pointer
• Each node contains at least
– A piece of data (any type)
– Pointer to the next node in the list
5
Linked List
• A linked list, or one-way list, is a linear
collection of data elements , called
nodes, where the linear order is
given by means of pointer
6
Linked List
A B C
Head
• A linked list is a series of connected
nodes
• Head : pointer to the first node
• The last node points to NULL
7
8
malloc & free
• void * malloc(n); -- allocates a memory
block of n bytes dynamically and returns
the base address of the block
• int * ptr;
ptr = malloc(sizeof(int))
1100
ptr 1100 1101
9
malloc & free
• void free(void * ptr); -- de-allocates
memory block (dynamically created)
pointed by ptr
• free(ptr)
10
Node structure in C
//in c++
struct NODE { class Node {
public:
int DATA; int data;
struct NODE * Next; Node* next;
};
};
struct NODE *ptr;
ptr = malloc(sizeof(struct NODE))
1100
ptr 1100
11
How to create in C?
Array 10 20 30 40
struct node{ struct node a={10,NULL}
int data; struct node b={20,NULL}
struct node* next; struct node c={30,NULL}
}; struct node d={40,NULL}
10 / 20 / 30 / 40 /
12
How to create in C?
struct node a={10,NULL}
struct node{ struct node b={20,NULL}
int data; struct node c={30,NULL}
struct node* next; struct node d={40,NULL}
};
a.next=&b;
b.next=&c;
c.next=&d;
10 20 30 40 /
13
How to create in C?
struct node a={10,NULL}
struct node{ struct node b={20,NULL}
int data; struct node c={30,NULL}
struct node* next; struct node d={40,NULL}
};
a.next=&b;
b.next=&c;
c.next=&d;
10 20 30 40
struct node* s=&a; //create head
s = s->next; //&s.next to travel
14
Simple Linked List Code
using namespace std;
class Node {
public: head->data = 1;
// assign data in first node
int data;
head->next = second;
Node* next; // Link first node with the second node
};
second->data = 2;
int main() second->next = third;
{
third->data = 3;
Node* head = NULL; third->next = NULL;
Node* second = NULL;
Node* third = NULL; return 0;
}
head = new Node();
second = new Node();
third = new Node(); 15
List Traversal
Head Data Link
16
Linked list traversing
Head Data Link
PTR
17
PTR: pointer that points the node currently processing
Link[ptr]: points to the next node to be process
Head Data Link
PTR = PTR - > Link
18
List Traversal
Let Head be a pointer to a linked list in
memory.
How to create an algorithm to print the
contents of each node of the list
19
List Traversal
Algorithm
1. set PTR = Head
2. Repeat step 3 and 4 while PTR
NULL
3. Print PTR->DATA
4. Set PTR = PTR -> LINK
5. Stop
20
List traversal code
int main()
{
#include <iostream> Node* head = NULL;
using namespace std; Node* second = NULL;
Node* third = NULL;
class Node {
// allocate 3 nodes in the heap
public: head = new Node();
int data; second = new Node();
Node* next; third = new Node();
};
head->data = 1; // assign data in first node
head->next = second;
void printList(Node* n) // Link first node with second
{
while (n != NULL) { second->data = 2; // assign data to second node
cout << n->data << " "; second->next = third;
n = n->next;
third->data = 3; // assign data to third node
} third->next = NULL;
}
printList(head);
return 0;
} 21
