Microsoft PowerPoint – 13_Chapter05_Lists_SHORT.pptx
1
CS 2211
Systems Programming
Part Eleven:
Lists
1
Nodes in Singly Linked Lists
• Nodes for our linked lists will be objects
dynamically created or deleted in the HEAP
• Each Node object in a singly linked list will
contain two member variables:
Node* nextItem value
Singly Linked List
.
head
Linked List object
Node objects
Data objects can be simple data (int, double, etc) or
complex data (arrays, structures or unions ) or
pointers to data outside each individual nodes
count
3
typedef struct node
{
void* dataPtr;
struct node* link;
} NODE;
// =================== createNode ====================
NODE* createNode (void* itemPtr)
{
NODE* nodePtr;
nodePtr = (NODE*) malloc (sizeof (NODE));
nodePtr->dataPtr = itemPtr;
nodePtr->link = NULL;
return nodePtr;
} // createNode
1 2
3 4
2
Linked List
.
Node object
dataPtr
link
Singly Linked List
.
Generic Linked List objects
void pointer void pointer void pointer
head count
3
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
// List ADT Type Defintions
typedef struct node
{
void* dataPtr;
struct node* next;
} NODE;
typedef struct
{
NODE* head;
int count;
} LIST;
definitions.h
Label Address Value
newDataP 326 – 329
sList 400 – 403
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403
…
list 510 -513 10100
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
5 6
7 8
3
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403
…
list 510 -513 10100
…
…
{ DM } 10100 – 10107
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403
…
list 510 -513 10100
…
…
head 10100 – 10103 NULL
{ DM } 10104 – 10107
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403
…
list 510 -513 10100
…
…
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403
…
list 510 -513 10100
…
…
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
9 10
11 12
4
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403 10100
…
…
…
…
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
#include “mainHeader.h”
int main (void)
{
// Local Definitions
int* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403 10100
…
…
…
…
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
15
Dynamic Linked Lists in C
END OF PART 1
To Add an Item to an Empty Linked List
head count
0.
Build the new node,
and put the new data
item pointer in it
.
data
13 14
15 16
5
To Add an Item to an Empty Linked List
head count
1
Make head point at
the new node, and
increment the list’s
size
.
data
#include “mainHeader.h”
int main (void)
{
// Local Definitions
char* newDataP;
LIST* sList;
sList = createList();
…
return 0;
} // main
LIST* createList(void)
{
LIST* list;
list= (LIST*) malloc (sizeof (LIST));
if (list)
{
list->head = NULL;
list->count = 0
} // if
return list;
} // createList
createList.c
Label Address Value
newDataP 326 – 329
sList 400 – 403 10100
…
…
…
…
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
…
LIST* sList;
sList = createList();
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList (sList, newDataP);
}
...
} // main
...
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
Label Address Value
newDataP 326 - 329
sList 400 - 403 10100
i 404 - 407 1
…
…
…
head 10100 - 10103 NULL
count 10104 - 10107 0
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
17 18
19 20
6
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
Label Address Value
newDataP 326 - 329
sList 400 - 403 10100
i 404 - 407 1
…
…
…
head 10100 - 10103 NULL
count 10104 - 10107 0
…
…
{ DM } 10210 - 10213
…
…
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
Label Address Value
newDataP 326 - 329 10210
sList 400 - 403 10100
i 404 - 407 1
…
…
…
head 10100 - 10103 NULL
count 10104 - 10107 0
…
…
{ DM } 10210 - 10213
…
…
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
Label Address Value
newDataP 326 - 329 10210
sList 400 - 403 10100
i 404 - 407 1
…
…
…
head 10100 - 10103 NULL
count 10104 - 10107 0
…
…
{ DM } 10210 - 10213 3
…
…
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
Label Address Value
newDataP 326 - 329 10210
sList 400 - 403 10100
i 404 - 407 1
…
…
…
head 10100 - 10103 NULL
count 10104 - 10107 0
…
…
{ DM } 10210 - 10213 3
…
…
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
21 22
23 24
7
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
…
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
{ DM } 10210 – 10213 3
…
…
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
{ DM } 10210 – 10213 3
…
…
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
{ DM } 10210 – 10213 3
{ DM } 10400 – 10407
…
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431 10400
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
{ DM } 10210 – 10213 3
{ DM } 10400 – 10407
…
…
…
…
…
…
…
…
…
…
…
25 26
27 28
8
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431 10400
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
{ DM } 10404 – 10407
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431 10400
head 10100 – 10103 NULL
count 10104 – 10107 0
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431 10400
head 10100 – 10103 NULL
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
I 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431 10400
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
…
…
…
…
…
…
…
29 30
31 32
9
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
i 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 10210
newPtr 428 – 431 10400
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
i 404 – 407 1
…
…
…
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
…
…
…
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->link = list->head;
if (list->count == 0)
list->rear = newPtr;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
P5-04b.h
…
for (int i = 1; i<=4; i++)
{
dataPtr = (char*) malloc (sizeof(char));
*dataPtr = 64 + i;
insertListEND(sList, dataPtr);
}
...
} // main
Label Address Value
newDataP 326 - 329 10210
sList 400 - 403 10100
i 404 - 407 1
…
…
…
head 10100 - 10103 10400
count 10104 - 10107 1
…
…
{ DM } 10210 - 10213 3
dataPtr 10400 - 10403 10210
next 10404 - 10407 NULL
…
…
…
…
…
…
…
…
…
…
10400
10400
10210
3
10210
36
Dynamic Linked Lists in C
END OF PART 2
33 34
35 36
10
To Add an Item to the Front of a Linked List
.
head count
1
Build the new node,
and put the new data
item in it,
make new node point
to the current front
node
To Add an Item to the Front of a Linked List
.
head count
2
Reset head so that it
points at the new
node, and increment
size of the linked list
...
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 10210
sList 400 – 403 10100
i 404 – 407 2
…
…
…
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
…
…
…
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303
…
…
…
…
…
…
…
…
…
37 38
39 40
11
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
…
…
…
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
…
…
…
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
list 420 – 423 10100
itemPtr 424 – 427 12300
…
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
…
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
list 420 – 423 10100
itemPtr 424 – 427 12300
newPtr 428 – 431
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
…
…
…
…
…
…
…
…
…
41 42
43 44
12
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
list 420 – 423 10100
itemPtr 424 – 427 12300
newPtr 428 – 431 12560
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
{ DM } 12560 – 12567
…
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
list 420 – 423 10100
itemPtr 424 – 427 12300
newPtr 428 – 431 12560
head 10100 – 10103 10400
count 10104 – 10107 1
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
list 420 – 423 10100
itemPtr 424 – 427 12300
newPtr 428 – 431 12560
head 10100 – 10103 10400
count 10104 – 10107 2
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
list 420 – 423 10100
itemPtr 424 – 427 12300
newPtr 428 – 431 12560
head 10100 – 10103 12560
count 10104 – 10107 2
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
…
…
…
…
…
…
…
45 46
47 48
13
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
…
…
…
head 10100 – 10103 12560
count 10104 – 10107 2
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
…
…
…
…
…
…
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 2
…
…
…
head 10100 – 10103 12560
count 10104 – 10107 2
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
…
…
…
…
…
…
…
12560
12560 10400
10400
51
Dynamic Linked Lists in C
END OF PART 3
To Add an Item to the Front of a Linked List
.
head count
2
Build the new node,
and put the new data
item in it,
make it point to the
current front node
49 50
51 52
14
To Add an Item to the Front of a Linked List
.
head count
3
Reset head so that it
points at the new
node, and increment
size of the linked list
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 17800
newPtr 428 – 431 21400
head 10100 – 10103 21400
count 10104 – 10107 3
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
…
…
…
…
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->link = list->head;
if (list->count == 0)
list->rear = newPtr;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
P5-04b.h
…
for (int i = 1; i<=4; i++)
{
newDataP = (char*) malloc (sizeof(char));
*dataPtr = 64 + i;
insertListEND(sList, dataPtr);
}
...
} // main
Label Address Value
newDataP 326 - 329 17800
sList 400 - 403 10100
i 404 - 407 1
list 420 - 423 10100
itemPtr 424 - 427 17800
newPtr 428 - 431 21400
head 10100 - 10103 21400
count 10104 - 10107 3
…
…
{ DM } 10210 - 10213 3
dataPtr 10400 - 10403 10210
next 10404 - 10407 NULL
{ DM } 12300 - 12303 6
dataPtr 12560 - 12563 12300
next 12564 - 12567 10400
{ DM } 17800 - 17803 9
dataPtr 21400 - 21403 17800
next 21404- 21407 12560
…
…
…
…
21400
12560 10400
10400
21400
12560
...
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 17800
sList 400 – 403 10100
…
…
…
…
head 10100 – 10103 21400
count 10104 – 10107 3
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
…
…
…
…
53 54
55 56
15
To Add an Item to the Front of a Linked List
.
head count
4
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 18300
newPtr 428 – 431 37300
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 1
list 420 – 423 10100
itemPtr 424 – 427 18300
newPtr 428 – 431 37300
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
P5-04b.h
37300
12560 10400
10400
21400
12560
37300
21400
…
for (int i = 1; i<=4; i++)
{
newDataP = (int*) malloc (sizeof(int));
*newDataP = i * 3;
insertList(sList, newDataP);
}
...
} // main
bool insertList (LIST* list, void* itemPtr)
{
NODE* newPtr;
if (!(newPtr =
(NODE*)malloc(sizeof(NODE))))
return false;
newPtr->dataPtr = itemPtr;
newPtr->next = list->head;
(list->count)++;
list->head = newPtr;
return true;
} // insertList
insertList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
i 404 – 407 1
…
…
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
57 58
59 60
16
61
Dynamic Linked Lists in C
END OF PART 4
Search for an Item in a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the data to
be retrieved
.
1
2 3
as you traverse the list
test the value the node points to
4
data data data data
36912
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
…
…
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
…
…
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
61 62
63 64
17
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
List 520 – 523 10100
value 524 – 527 6
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 37300
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 37300
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
65 66
67 68
18
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 21400
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 21400
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 12560
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 21400
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
69 70
71 72
19
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407
list 520 – 523 10100
value 524 – 527 6
nP 528 – 531 21400
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407 21400
…
…
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
NODE *rValue;
rValue = searchList(sList, 6);
if (rValue)
printf(“%d\n”,*(int *)rValue->dataPtr;);
…
} // main
NODE* searchList(LIST* list, int value)
{
NODE *nP;
for (nP = list->head; nP != NULL; nP = nP->next)
if (*(int*)nP->dataPtr == value)
return nP;
return NULL;
}
searchList.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
rValue 404 – 407 21400
…
…
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
76
Dynamic Linked Lists in C
END OF PART 5
73 74
75 76
20
To Remove an Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
1
2 3
as you traverse the list
test the value the node points to
data data data data
36912
To Remove an Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
1
as you traverse the list
store the address of the previous node in
a temporary variable
prev = cur;
cur = cur->next
cur = list->head;
( if not cur->data == value)
current
Previous
NULL
To Remove an Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
1
as you traverse the list
store the address of the previous node in
a temporary variable
prev = cur;
cur = cur->next
cur = list->head;
( if not cur->data == value)
current
previous
To Remove an Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
2
as you traverse the list
store the address of the previous node in
a temporary variable
prev = cur;
cur = cur->next
cur = list->head;
( if not cur->data == value)
previous current
77 78
79 80
21
To Remove an Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
2
as you traverse the list
store the address of the previous node in
a temporary variable
prev = cur;
cur = cur->next
cur = list->head;
( if not cur->data == value)
currentprevious
To Remove an Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
3
as you traverse the list
store the address of the previous node in
a temporary variable
prev = cur;
cur = cur->next
cur = list->head;
( if not cur->data == value)
currentprevious
To Remove an Item From a Linked List
head count
4
Set the link reference in
previous node to the
node being referenced
by the soon the be
deleted node
.
prev->next = cur->next;
currentprevious
To Remove an Item From a Linked List
head count
4
delete the node
free (node)
and decrement the
counter
.
free(cur->dataPtr);
free(cur);
currentprevious
81 82
83 84
22
To Remove an Item From a Linked List
head count
3
… and decrement the
counter
.
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.
1
prev = cur;
cur = cur->next
cur = list->head;
( if not cur->data == value)
current
Previous
NULL
IF Node is First Item From a Linked List
head count
4
Beginning at head,
traverse the list until
we reach the node that
points at the node to
be removed
.current
Previous
NULL
IF Node is First Item From a Linked List
list->head = cur->next;
free(cur->dataPtr);
free(cur);
To Remove an Item From a Linked List
head count
3
.
85 86
87 88
23
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 37300
prev 564 – 567 NULL
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 37300
prev 564 – 567 NULL
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 37300
prev 564 – 567 NULL
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 37300
prev 564 – 567 37300
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
89 90
91 92
24
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 21400
prev 564 – 567 37300
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 21400
prev 564 – 567 37300
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 12560
prev 564 – 567 21400
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 12560
prev 564 – 567 21400
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 12560
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
93 94
95 96
25
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 12560
prev 564 – 567 21400
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 10400
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 12560
prev 564 – 567 21400
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 10400
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 12560
prev 564 – 567 21400
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
{ DM } 12300 – 12303 6
dataPtr 12560 – 12563 12300
next 12564 – 12567 10400
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 10400
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
value 556 – 559 6
cur 560 – 563 12560
prev 564 – 567 21400
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 10400
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
97 98
99 100
26
…
deleteValue(sList, 6);
…
} // main
bool deleteValue(LIST* list, int value)
{
NODE *cur, *prev;
for (cur = list->head, prev = NULL;
cur != NULL && *(int*)cur->dataPtr != value;
prev = cur, cur = cur->next)
; /* NOTICE the empty loop ! */
if (cur == NULL)
return list; /* n was not found */
if (prev == NULL)
list->head = cur->next; /*n is the first node*/
else
prev->next = cur->next; /*n is some other node*/
free(cur->dataPtr);
free(cur);
return cur != NULL;
}
deleteValue.c
Label Address Value
newDataP 326 – 329 12300
sList 400 – 403 10100
…
…
…
…
head 10100 – 10103 37300
count 10104 – 10107 4
…
…
{ DM } 10210 – 10213 3
dataPtr 10400 – 10403 10210
next 10404 – 10407 NULL
…
…
…
{ DM } 17800 – 17803 9
dataPtr 21400 – 21403 17800
next 21404- 21407 10400
{ DM } 18300 – 18303 12
dataPtr 37300 – 37303 18300
next 37304- 37307 21400
…
102
Dynamic Linked Lists in C
END OF PART 6
Doubly-Linked Lists
• A common variation on linked lists is to have two
pointers to other nodes within each node: one to
the next node on the list, and one to the previous
node
• Doubly-linked lists make some operations, such as
deleting a tail node, more efficient
• Doubly-linked lists can have iterators for efficient
forward and backward traversals
– iterator can now have operator++ and operator- –
Doubly-Linked Lists
• Other operations, such as adding an item to
an ordered linked list, are easier to program
with doubly-linked lists
• Tradeoffs:
– Each node requires
4 (32 bit) additional bytes
–or-
8 (64 bit) additional bytes
101 102
103 104
27
Nodes in Doubly Linked Lists
• Each Node object in a doubly linked list will
contain three member variables:
Node* nextItem value
Node* prev
.
head count tail
4
.
Doubly-Linked List
To Remove Last Item From a Doubly-Linked List
.
head count tail
4
.
Note: We no longer need to
traverse the list.
Save a copy of the last data
object so that it can be
returned later
(Copy of data item from last node)
.
head count tail
4
.
Reset tail so that it points at
the node prior to the
original tail node
(Copy of data item from last node)
To Remove Last Item From a Doubly-Linked List
105 106
107 108
28
.
head count tail
4
.
Get rid of the successor
node of the new tail node
(Copy of data item from last node)
To Remove Last Item From a Doubly-Linked List
.
head count tail
3
.
Set the successor of the
new tail node to NULL,
decrement the size of the
list, and return the deleted
data object
.
To Remove Last Item From a Doubly-Linked List
To Remove Middle Item From a Doubly-Linked List
.
head count tail
4
.
Note: We no longer need to
traverse the list.
Save a copy of the last data
object so that it can be
returned later
(Copy of data item from node)
To Remove Middle Item From a Doubly-Linked List
.
head count tail
4
.
Note: We no longer need to
traverse the list.
Save a copy of the last data
object so that it can be
returned later
(Copy of data item from node)
current
cur->prev->next = cur->next ;
cur->next->prev = cur->prev ;
free(cur->dataPtr);
free(cur);
109 110
111 112
29
To Remove Middle Item From a Doubly-Linked List
.
head count tail
3
.
Note: We no longer need to
traverse the list.
Save a copy of the last data
object so that it can be
returned later
(Copy of data item from node)
cur->prev->next = cur->next ;
cur->next->prev = cur->prev ;
free(cur->dataPtr);
free(cur);
To Remove First Item From a Doubly-Linked List
.
head count tail
4
.
Note: We no longer need to
traverse the list.
Save a copy of the last data
object so that it can be
returned later
(Copy of data item from node)
current
head = cur->next ;
cur->next->prev = NULL;
free(cur->dataPtr);
free(cur);
To Remove First Item From a Doubly-Linked List
.
head count tail
3
.
Note: We no longer need to
traverse the list.
Save a copy of the last data
object so that it can be
returned later
(Copy of data item from node)
head = cur->next ;
cur->next->prev = NULL;
free(cur->dataPtr);
free(cur);
116
Dynamic Linked Lists in C
END OF PART 7
113 114
115 116
30
Circular Linked Lists Circular Linked Lists
• Circular linked lists avoid the use of null
references in their nodes
• Can be useful for certain algorithms
• Can also make programming simpler: fewer
special cases to consider
• Successor of tail node is the head node; in
doubly-linked list, predecessor of head node is
the tail node
Circular Doubly-Linked List
head count tail
3
120
Dynamic Linked Lists in C
END OF PART 8
END OF Dynamic Linked List
117 118
119 120
31
121