CS计算机代考程序代写 algorithm Microsoft PowerPoint - 13_Chapter05_Lists_SHORT.pptx

Microsoft PowerPoint – 13_Chapter05_Lists_SHORT.pptx

CS 2211
Systems Programming

Part Eleven:
Lists

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

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

Linked List

Node object

dataPtr
link

Singly Linked List

Generic Linked List objects

void pointer void pointer void pointer

head count

#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

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

#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

…
…
…
…
…
…
…
…
…
…
…
…
…
…
…

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

To Add an Item to an Empty Linked List

head count

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

…
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

…
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
…
…
…
…
…
…
…
…
…
…
…
…

(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
…
…
…
…
…
…
…
…
…
…
…
…

(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

…
…
…
…
…
…
…
…
…
…
…

(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

(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

…
…
…
…
…
…
…
…
…
…

(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
…
…
…
…
…
…
…
…
…
…

(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
…
…
…
…
…
…
…
…
…
…

(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

(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
…
…
…
…
…
…
…
…
…
…

(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
…
…
…
…
…
…
…
…
…
…

(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

(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

…
…
…
…
…
…
…
…
…

(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

…
…
…
…
…
…
…
…
…

(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

…
…
…
…
…
…
…
…
…

(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

(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

…
…
…
…
…
…
…
…

(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
…
…
…
…
…
…
…

(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
…
…
…
…
…
…
…

(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

(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
…
…
…
…
…
…
…

(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

Dynamic Linked Lists in C

END OF PART 3

To Add an Item to the Front of a Linked List

head count

Build the new node,
and put the new data
item in it,

make it point to the
current front node

49 50

51 52

To Add an Item to the Front of a Linked List

head count

Reset head so that it
points at the new
node, and increment
size of the linked list

(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

To Add an Item to the Front of a Linked List

head count

(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
…

(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

(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

Dynamic Linked Lists in C

END OF PART 4

Search for an Item in a Linked List

head count

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

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

…
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

…
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

…
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
…

Dynamic Linked Lists in C

END OF PART 5

73 74

75 76

To Remove an Item From a Linked List

head count

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

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

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

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

To Remove an Item From a Linked List

head count

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

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

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

delete the node
free (node)

and decrement the
counter

.
free(cur->dataPtr);
free(cur);

currentprevious

81 82

83 84

To Remove an Item From a Linked List

head count

… and decrement the
counter

head count

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

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

85 86

87 88

…
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

…
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

…
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

…
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

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

Doubly-Linked List

To Remove Last Item From a Doubly-Linked List

head count tail

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

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

head count tail

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

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

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

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

To Remove Middle Item From a Doubly-Linked List

head count tail

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

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

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

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

120

Dynamic Linked Lists in C

END OF PART 8

END OF Dynamic Linked List

117 118

119 120

121

Related Posts