Data Structures

and Algorithms with C

CHAPTER 4+5:
POINTER AND LINKED LISTS
 Main contents

 Pointer
 Singly Linked Lists
 Doubly Linked Lists
 Circular Linked Lists
 Linked Stack, Linked Queue (Chapter 6)
 Pointer
Variables in memory:
char c = “C”;
int a = 50;
float f = 3.45;
 Pointer
• Variables in programming languages include the value
of the variable and the memory address of the variable,
• Definition: A pointer is a memory address of another
variable.
• A pointer variable is a variable that its value is the
address of another variable (the variable stores the
memory address of another variable),
• A pointer is a variable. Thus it needs to be declared
before using
 Pointer
 Declaration:

Data_type *name_of_pointer_var;
where:
- Data_type is the basic type of a pointer,
- name_of_pointer_var is the
- Notation “*” is used in pointer variable declaration.
 Examples:
int *amount; //point to the address of an integer variable
float *GPA; //point to the address of a float variable
 Pointer

 Address of operator (&) returns the address of a

variable (reference operator).
 Indirection Operator (*) returns the value of the
memory address which is stored in its operand
(dereference operator).
 Pointer
 Example: What is the result of following program if
variable v1 is stored at address “0x6ffe04”
 Pointer
Type casting of Pointers
• The pointer variables have their own data type.
• The pointers do not support implicit type conversion.
• Pointer types can be converted to other pointer types
using the explicit type casting mechanism

Invalid
 Pointer
NULL Pointer
• A null pointer is a pointer value that points to no valid location
int *p = NULL;
• A null pointer is a constant pointer that is compatible with any
pointer
• A null pointer value is an address that is different from any valid
pointer
• Dereferencing a null pointer is meaningless, typically resulting
in a run-time error.
• In dynamic memory allocation in C, when calloc() or malloc()
function fails to allocate memory block, they return NULL
 Pointer
void Pointer
• A void pointer is a pointer, which may store the address of
any type of variable.
• The void pointer is also known as a type-less pointer or
generic pointer
• The indirection operator cannot be used with a void pointer.
• Void pointer allows violating the basic rule of the type
conversion of the pointer.

int a = 10; p = &a; Valid for

float b = 12.3; q = &b; void pointer
int *p; r = p;
float *q; q = r;
void *r;
 Pointer

Allowable Operations with Pointer

 Increment and decrement operations with pointer
variables.
 Subtraction of two pointer variables.
 Addition and subtraction of integer value with pointers.
 Relational operations between two pointer variables.
 Assignment Operation.

Note: Addition of two pointer variables of any type is not accepted.

 Pointer
Passing Addresses to Function
 A function can pass a value, as well as it can pass
addresses to the function i.e. can pass a reference
 The addresses of actual arguments in the calling function
are copied to formal arguments of the called function.
 The addresses of the actual arguments are copied to
formal arguments as a value, not a reference.
void swapf(float *a, float *b)
{
float temp;
temp = *a;
*a = *b;
*b = temp;
}
 Pointer
Function Returning Pointer
 The functions can return an integer, a floating point or any
other data type; as well as it can also return
a pointer.
 The format of function returning pointer:
data-type *function-name(argument-list)
Linked list - Introduction
• Arrays are useful in many applications but suffer from
two significant limitations
– The size of the array must be known at the time the code is
compiled
– The elements of the array are the same distance apart in
memory, requiring potentially extensive shifting when inserting a
new element
• This can be overcome by using linked lists, collections
of independent memory locations (nodes) that store
data and links to other nodes
Linked list
Difference between Array and Linked list
Linked list - Introduction

• Moving between the nodes is accomplished by following

the links, which are the addresses of the nodes
• There are numerous ways to implement linked lists, but
the most common utilizes pointers, providing great
flexibility.
Linked list - Introduction
Singly linked list

Doubly Linked Lists

Circular Linked Lists

Singly Linked Lists
• If a node contains a pointer to another node, we can
string together any number of nodes, and need only a
single variable to access the sequence
• In its simplest form, each node is composed of a datum
and a link (the address) to the next node in the sequence
• This is called a singly linked list
• Notice the single variable p used to access the entire list
• Also note the last node in the list has a null pointer
(NULL,  or \ )
Singly Linked Lists
• Example

a datum

a link
A node
 Singly Linked Lists (continued)

Fig. 3.1 A singly linked list

• The nodes in this list are objects created from the following definition
struct IntSLLNode {
int info;
IntSLLNode *next;
};
Singly Linked Lists - Advantages
• Linked list are dynamic data structures.
• Storage need not be contiguous.
• Efficient memory utilization. Here memory is not pre-
allocated. Memory is allocated whenever it is required.
• Insertion or deletion is easy and efficient (may be done
very fast, in a constant amount of times, independent of
the size of the list).
• The joining of two linked lists can be done by assigning
pointer of the second linked list in the last node of the
first linked list
Singly Linked Lists - Disadvantages

• The longer the list, the longer the chain of next pointers
that need to be followed to a given node
• This reduces flexibility, and is prone to errors
• An alternative is to use an additional pointer to the end of
the list
Singly Linked Lists
Operations on singly linked list
Singly Linked Lists
Create a list
//Define a generic type T
typedef int T;
// Define a node in the list
struct Node {
T data; // datum
Node * next; // link
};
// Define a list
struct List {
Node * head; // The pointer of the head
};
// Create an empty list
void listInit(List & list) {
list.head = NULL;
};
Singly Linked Lists
Check empty

// Check if the list is empty

bool listIsEmpty(List & list) {
return (list.head == NULL);
}
Singly Linked Lists
Insertion

• Inserting a node at the beginning of a list

• Inserting a node at the end of a list

• Insertion a node at the middle of a list

Singly Linked Lists
Insertion a node at the beginning of a list
The original singly linked list

A new node (v) is created with the link pointing to the head of list
first
node

v.next =
list.head;

Update pointer “head”: point to new node

Singly Linked Lists
Insertion a node at the beginning of a list
// e (element) is the datum that needs to be inserted.
void Ins_First(List & L, T e) {
// Make a new node
Node * v = new Node;
// set the datum for new node
v->data = e;
// New node is the first node
v->next = L.head;
// Update pointer “head”: point to new node.
L.head = v;
}
Singly Linked Lists
Printing all the contents (or all values of the nodes) of
a list
void printList(FNode *list){
FNode *p = list;
while(p!=NULL){//traverse a list
cout<<p->data<<" -> ";
p=p->next;
}
cout<<"NULL";
}
Singly Linked Lists
Example 1

Write a program with the functions as below

1. Define a singly linked list with the data in each node is a
float
2. Insert some nodes at the beginning of the list
3. Print all the Elements in the list
Singly Linked Lists
Insertion a node at the end of a list
The original singly linked list

Created a new node (v) with the link pointing to NULL

Let v is the last node of the list The old last

node (p)
Singly Linked Lists
Insertion a node at the end of a list
// e (element) is the datum that needs to be inserted.
void Ins_Last(List & L, T e) {
Node * v = new Node; // Make a new node
v->data = e;
v->next = NULL;
if (listIsEmpty(L)) L.head = v;
else
{
Node *p = L.head;
// Find the last node in the list.
while (p->next!=NULL) p=p->next;
p->next=v;//new node is the last node
}
}
Singly Linked Lists
Example 2

Write a program with the function as below

1. Define a singly linked list with the data in each node
is a float
2. Insert some nodes to the end of the list
3. Enter a float value X, find the position of X in the list.
Singly Linked Lists
Insertion a node at the middle of a list

pos -1 pos

Head

NULL
Singly Linked Lists
Example 3

Write a program with the function as below

1. Define a singly linked list with the data in each node is a
float
2. Insert some nodes at the beginning of the list
3. Enter a position (pos) that you want to add a node and a
value X. Insert the node with the value X into the list at the
position pos
Singly Linked Lists
Deletion

• Deleting a node at the beginning of a list

• Deleting a node at the end of a list

• Deleting a node at the middle of a list

 38

Singly Linked Lists

Deleting a node at the beginning of a list
head->next

head = head->next
 39

Singly Linked Lists

Deleting a node at the beginning of a list
void Del_First(List & L) {
// Keep the address of the head
Node * old = L.head;

// Update the head.

L.head = L.head->next;

// release memory of the first node in original list

delete old;
}
 40

Singly Linked Lists

Deleting a node at the end of a list
prev cur

prev->next=NULL

Step 1: If head points to NULL, return. The linked list is empty – there is no node.
Step 2: If the first node points to NULL – there is only one node in the linked list, delete the
first node and assign NULL to head.
Step 3: Point prev to first node and cur to second node.
Step 4: Keep moving prev and cur (prev = prev->next, cur = cur->next) until cur->next is NULL.
Step 5: If cur->next is NULL, set prev->next equals to NULL and delete cur.
Singly Linked Lists
Deletion a node at the middle of a list
pos=1 p temp = p->next

p->next = p->next->next
void *deleteAt(List &L, int pos){
node *p = L.head;
for (int i = 0; i < pos-1; i++){ p = p->next; }
node *temp = p->next;//the position of the node that needs to be deleted
p->next = p->next->next; //ignore the node in position pos
delete(temp); //release the memory of deleted node
}
Singly Linked Lists
Example

Write a program with the function as below

1. Define a singly linked list with the data in each node
is a float
2. Insert some nodes to the end of the list
3. Enter a float value X, find the position of X in the list.
4. Delete two first nodes in the list
Singly Linked Lists
Destroy a singly linked list

void listDestroy(List & L) {

while (!listIsEmpty(L))
Del_First(list); // Delete the first node
//until the list is empty
}
Singly Linked Lists
Complexity of a singly linked list

Comparison of Array and Linked list

 Doubly Linked Lists
• The difficulty in deleting a node from the end of a singly
linked list points out one major limitation of that structure
• We continually have to scan to the node just before the end in
order to delete correctly
• If the nature of processing requires frequent deletions of that
type, this significantly slows down operations
• To address this problem, we can redefine the node structure
and add a second pointer that points to the previous node
• Lists constructed from these nodes are called doubly linked
lists,
 Doubly Linked Lists

typedef int T;
// define a node
struct DNode {
T data; // date
DNode * next; // point to the next node
DNode * prev; // point to previous node
};
// Define a doubly linked list
struct DList {
DNode * header; // point to the beginning node (Pseudo node)
DNode * trailer; // point to ending node (Pseudo node)
DNode * currentPos; // point to current node
};
Doubly Linked Lists (continued)

• The methods that manipulate these types of lists are

slightly more complicated than their singly linked
counterparts
• However, the process is still straightforward as long as
one keeps track of the pointers and their relationships
• We’ll look at two: inserting a node to a list and removing
a node from a list
 50

Doubly Linked Lists

Insert a node to a doubly linked list before current pos

Insert to the front of

v->prev this node (v) v->next

New node (u)

(v->prev )->next = u
u->next = v

u->prev= v->prev v->prev= u

 51

Doubly Linked Lists

Insert a node to a doubly linked list before current pos
// Before inserting: keep v->prev and v
// v is the current node;
// e is the element that need to be inserted.
void dlistInsert(Dlist & L, T e) {
DNode * v = list.currentPos; // get current node
DNode * u = new DNode; // make a new node

u->data = e; // Set datum for new node

u->next = v; // Set pointer to the next node
u->prev = v->prev; // Set pointer to the previous node

v->prev->next = u; //change the connection

v->prev = u; //change the connection
}
 52

Doubly Linked Lists

Delete a node to a doubly linked list at current pos
Current pos(v)

Before(u) Deleted node (v) After (w)

u->next = w;

w->prev = u;

current pos (w)

 53

Doubly Linked Lists

Insert a node to a doubly linked list at current pos

// Keep three nodes: prev(u)  current (v)  next(w)

void dlistRemove(DList & L) {
DNode * v = L.currentPos;
DNode * u = v->prev;
DNode * w = v->next;

u->next = w;
w->prev = u;

delete v;

L.currentPos = w;
}
Circular Lists

• Another useful arrangement of nodes is the circular list;

in this structure the nodes form a ring

A circular singly linked list

• A circular linked list is the variation of singly linked list in
which the last node points to the first node
of the list. The circular linked lists have neither a
beginning nor an end.
 Circular Lists
• Two methods to know if a node is the first node or not.
- Either an external pointer, list, points the first node or

- A header node is placed as the first node of the circular

list.

• The header node can be separated from the others by

either having a sentinel value as the info part or having a
dedicated flag variable to specify if the node is a header
node or not.
 Circular Lists
• A special pointer named as cursor is added in order to point to
the beginning of the list (front).
Circular Lists (continued)

typedef int T;
struct CNode {
T data; // Datum
CNode * next; // Link
};
struct CList {
CNode * cursor;
};
 Circular Lists
• Add a node to right after the cursor
void clistInsert(DList & L, T e) {
CNode * v = new CNode;
v->data= e;
if (L.cursor == NULL) { //empty list
v->next = v;
L.cursor = v;
}
else {//non-empty list
v->next = L.cursor->next;
L.cursor->next = v;
}
}
 Circular Lists
• Delete a node right after the cursor
void clistRemove(CList & L) {
// Keep the address of the node
CNode * old = L.cursor->next;
if (old == cursor) // The list has unique node
cursor = NULL;
else
cursor->next = old->next;
delete old;
}
 Summary
• A linked list is a linear ordered collection of finite
homogeneous data elements called node.
• The linked list overcomes the demerits of array
in terms of memory allocation.
• Linked list can be classified into 4 types single
linked list, circular linked list, doubly linked list
and circular doubly linked list.
• Polynomial addition can be done using linked
list.
• Addition, Deletion and Insertion of a node in a
linked list is faster than array.
 Exercises
1. Write an algorithm to insert a data X after a specific data
item Y in the linked list.
2. Write a function to delete the nth node of a singly linked list.
The error conditions are to be handled properly.
3. Write an algorithm to delete any node from the singly liked
list where the key value of the node is known.
4. Write an algorithm to delete a node from a doubly linked list.
5. Write an algorithm to delete all nodes having greater than a
given value, from a given singly linked list.
6. Write a program to INSERT and DELETE node in a circularly
doubly linked list. Display the elements of the list.
Excercises
I. Write a program with the function as below
1. Define a singly linked list with the data in each node is a
float
2. Insert some nodes to the list
3. Enter a float X and find the position of X in the list.
4. Print all the elements in the list
Let the users select the functions by using the below menu:
Excercises
II. Write a program with the function as below
To manage the information of students, a struct is defined as
below:
struct sinhvien{
string maSV;
string hotenSV;
string lop;
double diem;
};
Excercises
Define a singly linked list with the data in each node is the
information of a student and write the program to perform
following functions:
1. Insert some nodes to the list (use while loop)
2. Count the number of nodes in the list.
3. Enter a Student ID and print all the information of this
student in the list (if exists).