Data Structures
Lecture 4: Linked List
By
Asst. Professor
Lovely Professional University, Punjab
Outlines
• Introduction
• Why Linked List?
• Types of Linked List
• Memory Representation of Linked Lists
• Difference between Singly Linked List and Arrays
• Review Questions
Introduction
A linked-list is a linear collection of data items which are
connected together via links.
Linked List is a sequence of links which contains items.
Each link contains a connection to another link. Linked
list the second most used data structure after array.
• 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.
Linked List
• A singly linked list is a
concrete data structure
consisting of a sequence of next
nodes
• Each node stores
– element
– link to the next node node
element
A B C D
Key Points
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
• The size of the arrays is fixed: So we must know the upper limit on the number of
elements in advance. Also, generally, the allocated memory is equal to the upper
limit irrespective of the usage, and in practical uses, upper limit is rarely reached.
• Inserting a new element in an array of elements is expensive, because room has to
be created for the new elements and to create room existing elements have to
shifted.
• For example, suppose we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040, …..].
And if we want to insert a new ID 1005, then to maintain the sorted order, we
have to move all the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are
used. For example, to delete 1010 in id[], everything after 1010 has to be moved.
• So Linked list provides following two advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
Linked lists have following drawbacks:
• Random access is not allowed. We have to access
elements sequentially starting from the first node. So
we cannot do binary search with linked lists.
• Extra memory space for a pointer is required with
each element of the list.
Some Notations for use in algorithm
• p: is a pointer
• node(p): the node pointed to by p
• info(p): the information portion of the node
• next(p): the next address portion of the node
• getnode(): obtains an empty node
• freenode(p): makes node(p) available for reuse even if
the value of the pointer p is changed.
Memory Representation
• Linked lists are maintained in memory using linear arrays or
Parallel arrays.
INFO LINK Start 1
2
2 A 6
3 E 9
4 C 7
5
6 B 4
7 D 3
8
9 F 0
10
Memory Representation (2)
• Multiple lists in memory
INFO LINK
Start1 1 S4 0
2
2 A 6
3 E 9
Start 2 4 10 C 7
5 S2 8
6 B 4
7 D 3
8 S3 1
9 F 0
10 S1 5
Memory Representation (3)
• INFO part of a node may be a record with multiple data items.
• Records in memory using Linked lists
Start Name Age Sex LINK
2
1
2 A 19 M 6
3 E 21 M 9
4 C 20 F 7
5
6 B 19 F 4
7 D 22 M 3
8
9 F 20 F 0
10
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
Single linked list
Node is represented as:
struct node {
int data;
struct node *next;
}
Circular,doubly link list
Difference between Singly Linked List and
Arrays
Singly linked list Array
Elements are stored in Elements are stored in
linear order, accessible linear order, accessible
with links. with an index.
Do not have a fixed size. Have a fixed size.
Cannot access the previous Can access the previous
element directly. element easily.
No binary search. Binary search.
STEP 1: SET PTR = HEAD
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 7
END OF IF
STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR != NULL
STEP 5: PRINT PTR→ DATA
STEP 6: PTR = PTR → NEXT
[END OF LOOP]
Review Questions
• Why we need Linked List?
• What are the two different Fields in a node of linked list.
• How Linked lists are different from Arrays?
• Why Binary search is not possible in Linked list?
• What is the difference between Circular Linked List and
Doubly Linked List?
