Transcript linked list.

Abstract Data Structures
Self-referential data structures,
dynamic memory allocation, linked
lists, stacks, queues, trees …
Outline
 Self-referential data structures
 Statically versus Dynamically allocated memory
 Concept of linked structures
 Linked lists
 Stacks and Queues
 Trees and advanced data structures
Self-referential data structures
 In previous lectures on struct’s we introduced the notion
of self-referential
data {structures
struct NodeStruct
;
 These int
areIDstruct’s
that contain a pointer sub-field that is
char
intended
toName[50]
point at a; struct of the same type definition
double Score ;
 Example:
struct NodeStruct * NextPtr ;
};
typedef struct NodeStruct Node_t ;
Node_t Node = { 0, “”, 0.0, NULL }, Node2 ;
Node_t * NodePtr = &Node ;
Node.NextPtr = &Node2 ;
NodePtr->NextPtr = &Node2 ;
// This way …
// … or that way!
Statically vs Dynamically allocated memory
 C provides for support of a logical (ie. conceptual) model
in which user allocated memory (for a given program) is
divided into several distinct blocks
 These include a block for code, for static data, for stack
data, for buffers (I/O) and for dynamical memory allocation
(on the Heap)
 When programmers write programs, they utilize names to
declare variables and data structures so that they can
refer to those memory locations within their code
 These named variables refer to a statically assigned
Namespace (once compiled, names and logical locations do
not change)
Statically vs Dynamically allocated memory
 We are now going to consider dynamically allocated
memory and techniques for exploiting it
 This is done at execution time, hence we cannot create
NodePtr = malloc( sizeof( Node_t ) ) ;
variable names to refer to locations – we must use
pointers
instead != NULL )
if( NodePtr
printf(
“Memory free()
allocation
) ; are
 We focus
on malloc(),
andsuccessful!\n”
sizeof – all three
else
important!
 Example:printf( “Memory not allocated!\n” ) ;
free( NodePtr ) ;
struct Nodetype { struct Nodetype * NextPtr ; . . . } ;
typedef struct Nodetype Node_t ;
Node_t * RootPtr ;
Memory block
used for
program
variables with
assigned
names
Statically
allocated
namespace
Memory block used for
dynamically allocated
blocks for storing data,
each block addressable
only using pointers (no
names of variables!)
Dynamically allocated
memory – The Heap
RootPtr
Pointer
Data
Pointer
sizeof( Node_t )
Data
Pointer
Data
NULL
Concept of linked structures
 We will be creating dynamic (ie. runtime) data
structures that will contain pointers to other
structures
 These are called linked structures.
 Example:
Node_t Node1, Node2 ;
Node1.NextPtr = &Node2 ; // points at Node2
Node2.NextPtr = NULL ;
// points nowhere!
Node1
Data
Node2
Pointer
Data
NULL
Linked lists
 The concept of a linked list refers to a set of dynamically
allocated structures that contain pointer sub-fields, so
that each pointer points at another allocated structure
 By linking all elements of the set together, starting from a
known address location, the entire set is called a linked list.
 All linked lists must have an associated root pointer that
is a named pointer variable. This provides the known
address location to enter the list
 There will be a last, or final, element and that one must
have a NULL value in its link pointer to indicate the
logical end-of-list.
 There are several kinds of linked list structures
 Singly linked list
 Doubly linked list
Linked lists
 To illustrate the concept with code, we consider the
example problem
typedef struct { int ID ;
 char
InputName[50]
data from
; a direct access file into a linked list.
double Score ; } Payload_t ;
struct NodeStruct {
Payload_t Data ;
struct NodeStruct * NextPtr ; } ;
typedef struct NodeStruct Node_t ;
FILE * cfPtr ;
Node_t * NodePtr, * Nptr, * RootPtr ;
int PayloadSize = sizeof( Payload_t ), NodeSize = sizeof( Node_t ) ;
Linked lists
 Example – continued
 Always deal with the named root pointer first as a
special case – Head of the List
cfPtr = fopen( “DAFile.dat”, “rb” ) ;
RootPtr = malloc( NodeSize ) ;
fread( RootPtr, PayloadSize, 1, cfPtr ) ;
RootPtr->NextPtr = NULL ;
RootPtr
Pointer
Data
0
Linked lists
RootPtr
Pointer
Example – continued
Data Nxt
0
 And now deal with the dynamically allocated list nodes
and links
Data Nxt
Data
Nptr = RootPtr ;
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Nptr->NextPtr = NodePtr ;
Nptr = NodePtr ;
Nptr->NextPtr = NULL ;
}
fclose( cfPtr ) ;
Linked lists
 Another example: Traversal of a list to find an ID
 Note that this is a sequential search with complexity
NptrO(N)
= RootPtr
// Head
of the list
for a ;list with
N nodes
while( Nptr != NULL) ) {
// list traversal loop
if( Nptr->Data.ID == IDval ) break ;
Nptr = NPtr->NextPtr ;
// search criterion
// point at successor (next) element
}
if( Nptr != NULL )
printf( “ID = %d, Name = %s, Score = %lf\n”,
Nptr->Data.ID, Nptr->Data.Name, Nptr->Data.Score ) ;
else
printf( “ID: %d not found\n”, IDval ) ;
Linked lists
 And another example:
Traversal of a list to output data to stdout
 Always start from the named root pointer
Nptr = RootPtr ;
while( Nptr != NULL ) {
printf( “ID = %d, Name = %s, Score = %lf\n”,
Nptr->Data.ID, Nptr->Data.Name, Nptr->Data.Score ) ;
Nptr = Nptr->NextPtr ;
}
Linked lists
 Deletion of a list
 Also called de-allocation of memory
IMPORTANT POINT !
 This is an extremely important issue for programmers
Since memory blocks are allocated in unpredictable ways
Nptr (effectively
= RootPtr ; random), freeing those blocks may leave gaps,
or holes, in the Heap.
while( Nptr != NULL) ) { // Traverse the list
A systematic freeing up of all blocks eventually returns the
Heap//to
its original
unallocated
state. is important
CAUTION:
Order
of statements
NodePtr = Nptr ;
// 1. Save current node address
For every malloc()
must be
Nptr = NodePtr->NextPtr
; // 2.call
Pointthere
at successor
node
callmemory
!
free( NodePtr ) ; a matching
// 3.free()
Release
for node
}
RootPtr = NULL ;
// list is now empty!
Linked lists
 Input data into a linked list so that it is sorted with
each insertion of a node – Insertion Sort
 Recall from a previous example:
typedef struct { int ID ;
char Name[50] ;
cfPtr
= fopen(
double
Score ;“DAFile.dat”,
} Payload_t ;“rb” ) ;
struct NodeStruct {
RootPtr
= malloc(
Payload_t
Data ; NodeSize ) ;
fread(
PayloadSize,
struct RootPtr,
NodeStruct
* NextPtr ;1,
} ;cfPtr ) ;
RootPtr->NextPtr = NULL ;
typedef struct NodeStruct Node_t ;
FILE * cfPtr ;
Node_t * NodePtr, * Nptr, * RootPtr ;
int PayloadSize = sizeof( Payload_t ), NodeSize = sizeof( Node_t ) ;
Linked lists
 We must consider three different special cases
 1. Insert at Head of List
 2. Insert between two list nodes
 3. Insert at End of List
1
3
2
RootPtr
Pointer
Data Nxt
Data Nxt
Data
0
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
}
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
NodePtr->NextPtr = RootPtr ;
RootPtr = NodePtr ;
}
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
 Input data from a direct access file into a linked list
 Here is a complete listing of the C code for this
algorithm
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
NodePtr->NextPtr = PrevNodePtr ;
PrevNodePtr->NextPtr = NodePtr ;
break ;
}
else {
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;
}
}
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
}
}
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
Pointer
Data
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
}
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
NodePtr->NextPtr = RootPtr ;
\\ ASSUMPTION: File has been opened using
RootPtr = NodePtr ;
}
while( ! feof( cfPtr ) ) {
else {
NodePtr = malloc( NodeSize ) ;
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID
\\ Logic to) {find where to insert
NodePtr->NextPtr = PrevNodePtr ;
\\ in the singly linked list.
PrevNodePtr->NextPtr = NodePtr ;
break ;
}
}
else {
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;
}
}
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
}
}
cfPtr
this inputted data block
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
RootPtr
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
Pointer
}
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
NodePtr->NextPtr = RootPtr ;
RootPtr = NodePtr ;
}
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
if( RootPtr == NULL
){
NodePtr->NextPtr = NULL ;
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID
RootPtr) {= NodePtr ;
NodePtr->NextPtr = PrevNodePtr ;
}
PrevNodePtr->NextPtr = NodePtr
;
break ;
}
else {
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;
}
}
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
}
}
Data
0
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
}
RootPtr
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
NodePtr->NextPtr = RootPtr ;
RootPtr = NodePtr ;
Pointer
}
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
Data
?
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
else if( ;NodePtr->Payload.ID < RootPtr->Payload.ID
NodePtr->NextPtr = PrevNodePtr
PrevNodePtr->NextPtr = NodePtr ;
NodePtr->NextPtr = RootPtr ;
break ;
RootPtr = NodePtr ;
}
else {
}
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;else {
}
\\ Locate insertion point in SL list
}
} NULL ) {
if( PrevNodePtr->NextPtr ==
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
}
}
){
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
RootPtr
NodePtr
= malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
Pointer
Data Nxt
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
}
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
NodePtr->NextPtr = RootPtr ;
RootPtr = NodePtr ;
}
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
Data Nxt
Data
0
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
}
}
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
NodePtr->NextPtr = PrevNodePtr ; NodePtr->NextPtr = NPtr ;
PrevNodePtr->NextPtr = NodePtr ; PrevNodePtr->NextPtr = NodePtr ;
break ;
break ;
}
else {
}
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;
else {
}
PrevNodePtr = Nptr ;
}
if( PrevNodePtr->NextPtr == NULL ) {
Nptr = Nptr->NextPtr ;
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;}
}
}
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr
= NodePtr ;
RootPtr
}
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
Pointer = RootPtr ;
Data Nxt
NodePtr->NextPtr
RootPtr = NodePtr ;
}
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
 Rgn
 Input data from a direct access file intoData
a linked
list
0
 \iggffi
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
while( Nptr != NULL ) {
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
NodePtr->NextPtr = PrevNodePtr ;
PrevNodePtr->NextPtr = NodePtr ;
break ;
}
else {
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;
}
}
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
}
}
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
if( RootPtr == NULL ) {
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
}
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) {
NodePtr->NextPtr = RootPtr ;
RootPtr = NodePtr ;
}
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
WHEW !
This example illustrates the Top-Down approach where the
original problem has been broken down into sub-problems.
These are organized methodically, and the algorithm
while( Nptr != NULL ) {
developed accordingly.
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
NodePtr->NextPtr = PrevNodePtr ;
PrevNodePtr->NextPtr = NodePtr ;
break ;
There are many details to consider and care must be
}
taken when writing code with pointers, ensuring that
else {
PrevNodePtr
;
the= Nptr
order
of statements is correct.
Nptr = Nptr->NextPtr ;
}
}
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
Always test code !!
}
}
\\ ASSUMPTION: File has been opened using cfPtr
while( ! feof( cfPtr ) ) {
NodePtr = malloc( NodeSize ) ;
fread( NodePtr, PayloadSize, 1, cfPtr ) ;
Linked lists
\\ USING LINKED LIST FUNCTIONS
if( RootPtr == NULL ) {
\\ ASSUMPTION: File has been opened using cfPtr
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
while( ! feof( cfPtr ) ) {
}
NodePtr = malloc( NodeSize ) ;
else if(NodePtr->Payload.ID < RootPtr->Payload.ID ) { fread( NodePtr, PayloadSize, 1, cfPtr ) ;
NodePtr->NextPtr = RootPtr ;
NodePtr->NextPtr = NULL ;
RootPtr = NodePtr ;
}
Nptr = FindNode ( RootPtr, NodePtr->Payload.ID ) ;
else {
Node_t * PrevNodePtr = RootPtr ;
Nptr = RootPtr->NextPtr ;
InsertNode( RootPtr, Nptr, NodePtr ) ;
while( Nptr != NULL ) {
}
if( NodePtr->Payload.ID < NPtr->Payload.ID ) {
NodePtr->NextPtr = PrevNodePtr ;
\\ This still leaves the functions to write, but it makes
PrevNodePtr->NextPtr = NodePtr ;
break ;
\\
it easier to understand the primary algorithm,
}
\\
and the start of the Top-Down design process.
else {
PrevNodePtr = Nptr ;
Nptr = Nptr->NextPtr ;
}
}
if( PrevNodePtr->NextPtr == NULL ) {
NodePtr->NextPtr = NULL ;
PrevNodePtr->NextPtr = NodePtr ;
}
}
}
Linked lists
 From the previous example it is seen that developing and using
functions with well defined algorithms is worthwhile when working
with dynamically allocated list data structures
 This separates high-level intention from low-level details
 Design focuses on Use-Cases, while details focus on how it works
 Some other example functions to consider:







Node_t * FindNode ( Node_t * Head, int IDval ) ;
void * InsertNode ( Node_t * Root,
Node_t * InsertPtr,
Node_t * InsertNodePtr ) ;
Node_t * FindLastNode ( Node_t * Head ) ;
void * OutputList ( Node_t * Head ) ;
void * DeleteList ( Node_t * Head ) ; // deallocate all nodes
int isEmpty( Node_t * Head ) ; // only need to test if Head == NULL
long int ListLength( Node_t * Head ) ; // count number of nodes
Doubly linked lists – Conceptual View
struct NodetypeDL {
Payload_t Data ;
struct NodetypeDL * PrevPtr ;
struct NodetypeDL * NextPtr ;
};
typedef struct NodetypeDL Node_tDL ;
TailPtr
Node_tDL * HeadPtr = NULL, * TailPtr = NULL ;
Pointer
HeadPtr
Pointer
Data NULL Nxt
Data
Prv Nxt
Data Prv NULL
Doubly linked lists
 Doubly linked lists feature two self-referential pointers, usually called
Predecessor (Previous) and Successor (Next) links
 There are two named pointers, usually called Head and Tail pointers,
the latter pointing to the last node in the list
 Traversal can be performed in both directions
 Limited traversals (to adjacent, or nearby, nodes) can be performed in
both directions
 Typical operations are similar to those for singly linked lists

InsertNode, DeleteNode, DeleteList, FindNode, and so on
Bi-directional traversal
Doubly linked lists – Useful functions
 InsertHeadNode
 InsertTailNode
 FindNodebyID
 InsertNodebyID
 DeleteNodebyID
 DeleteList
Assume that Nptr points to the data structure to
Doubly linked \\\\lists
– Useful functions
be inserted at the head of the list, and it is fully
 InsertHeadNode
 InsertTailNode
\\ initialized, including both Next and Prev pointers
\\ with NULL values.
\\ Note: Both head and tail pointer arguments can be
\\
modified (use call-by-reference).
 FindNodebyID
 InsertNodebyID
 DeleteNodebyID
void InsertHeadNode( StackNodePtr_t * Hptr,
StackNodePtr_t * Tptr,
StackNodePtr_t Nptr ) {
 DeleteList
if( *Hptr == NULL )
\\ empty list, update tail
*Tptr = Nptr ;
else
\\ update new node to point
Nptr->NextPtr = *Hptr ; \\ to rest of list
*Hptr = Nptr ;
return ; // success
\\ update head and exit
}
\\ NOTE: It is possible to achieve this in different
\\
ways.
Assume that Nptr points to the data structure to
Doubly linked \\\\lists
– Useful functions
be inserted at the tail of the list, and it is fully
 InsertHeadNode
 InsertTailNode
\\ initialized, including both Next and Prev pointers
\\ with NULL values.
\\ Note: Both head and tail pointer arguments can be
\\
modified (use call-by-reference).
 FindNodebyID
 InsertNodebyID
 DeleteNodebyID
void InsertTailNode( StackNodePtr_t * Hptr,
StackNodePtr_t * Tptr,
StackNodePtr_t Nptr ) {
 DeleteList
if( *Tptr == NULL )
\\ empty list, update head
*Hptr = Nptr ;
else
\\ update new node to point
Nptr->PrevPtr = *Tptr ; \\ to rest of list
*Tptr = Nptr ;
return ; // success
}
\\ update tail and exit
\\ Assume that IDval contains the search value and
Doubly linked
lists – Useful functions
\\ Hptr points to the head of the list.
\\ Returns a pointer to the first node containing IDval,
 InsertHeadNode \\ otherwise returns NULL.
 InsertTailNode
StackNodePtr_t * FindNodebyID( StackNodePtr_t Hptr,
 FindNodebyID
int IDval ) {
StackNodePtr_t Nptr ;
 InsertNodebyID
 DeleteNodebyID
if( *Hptr == NULL ) \\ empty list
return NULL ;
else
\\ search list
Nptr = Hptr ;
while( Nptr != NULL ) {
if( Nptr->Payload.ID == Idval )
return Npr ;
\\ search successful
Nptr = Nptr->NextPtr ;
}
return NULL ;
 DeleteList
}
Linked lists – Some Deeper Details
 Logical model view of the Heap Space
 Memory allocation model
 Based on heap pointers
 Unpredictable address associations with the memory block
 Requires care – once a pointer is lost, the memory block (and all
data inside it) is lost and cannot be accessed
 Management
 Overhead costs – time and space
 Allocation Tables and Heap Limits
 Holes and fragmentation
 Defragmentation
?
RootPtr
Pointer
Data Nxt
?
Data Nxt
Data
0
Stacks and Queues
 There are two kinds of singly linked list structures that merit special
attention
 A Stack is a linked list with an access pointer called the Stack
Pointer, and whose nodes are added or deleted only at the beginning
of the list
 They are referred to as LIFO (Last In, First Out) lists
 A Queue is a linked list with two access pointers, called Head and
Tail, and whose nodes are added only to the Tail, or deleted only
from the Head of the list
 They are referred to as FIFO lists (First In, First Out)
Stacks
 There are two basic operations on stacks. Both are applied only at
the beginning of the list, otherwise called the Top of the Stack
 PUSH – insert a new node at the top of the stack
 POP – remove (delete) a new node from the top of the stack
 The named entry pointer is typically called the Stack Pointer
 \\ ASSUMPTIONS:
struct stackNode {
Data_t Data ;
struct stackNode * Nextptr ;
}
typedef struct stackNode StackNode ;
typedef StackNode * StackNodePtr_t ;
StackNodePtr_t StackPtr = NULL ;
LIFO
StackPtr
Pointer
Data Nxt
Data Nxt
Data
0
Stacks – Push()
 Push() inserts a node into




the first list position of the
stack
The new top-of-stack node
must point to the rest of the
list
The stack pointer must point
at the new top-of-stack node
Account for possible error
This is one alternative
coding of Push() – there are
others (eg. textbook)
StackPtr
Pointer
Top-of-stack
node
Data Nxt
StackNodePtr Push( StackNodePtr * SP,
Data_t D ) {
StackNodePtr NewPtr ;
NewPtr = malloc( sizeof( StackNode ) ) ;
if( NewPtr == NULL ) return NULL ;
Copy( NewPtr->Data, D ) ;
NewPtr->NextPtr = NULL ;
if( *SP != NULL )
NewPtr->NextPtr = *SP ;
*SP = NewPtr ;
return SP ;
}
\\ USE CASE
if( Push( &stackPtr, Data ) != NULL )
printf( “Push to stack successful\n” ) ;
else
printf( “Allocation failed, no Push\n” ) ;
Data Nxt
Data
0
Stacks – Pop()
int Pop( StackNodePtr * SP, Data_t * Dptr ) {
StackNodePtr tempPtr ;
Data_t D ;
 Pop() obtains and
returns
the payload
from
top-of-stack
if( *SP
== NULL
) return 0 ;data
\\ Stack
is the
empty
so fail
node, then it removes this node from the stack
Copy( (*SP)->Data, Dptr ) ; \\ Copy-return payload data
 A return mechanism must be chosen and implemented for the
tempPtr = (*SP)->NextPtr ; \\ Get address of next node
payload data free( *SP ) ;
\\ Deallocate top node
tempPtrdirectly
;
\\ Update
stack
pointer
 Scalar data can*SP
be =returned
through
function
return
statements –
this limits the ability to report errors such as an empty stack
return 1 ;
\\ Success is TRUE
 Call-by-reference is always useful, but necessary for complex data
}
structures
\\ USE
CASE
DataRec
 The stack pointer
must
be:: Assume:
updated Data_t
to point
at the; second node,
\\
StackNodePtr * StackPtr ;
which then becomes
the new top-of-stack
node
 The used node
then
de-allocated
(and
if( is
Pop(
&StackPtr,
&DataRec
) ) its memory block can be
printf( “ID = %d\n”, DataRec.ID ) ;
re-used)
else
printf( “No data found on empty stack\n” ) ;
Top-of-stack
StackPtr
Pointer
node
Data Nxt
Data Nxt
Data
0
Queues
 The basic queue is a singly linked list
with two pointers, Head and Tail
 There are two fundamental operations
 enqueue() – insert a node at the Tail position
 dequeue() – obtain payload data from the node at the
Head position, then delete the node
TailPtr
Enqueue
Pointer
HeadPtr
Pointer
Dequeue
Data Nxt
Data Nxt
Data
0
Queues
NodePtr_t enqueue( NodePtr_t * NQP, Data_t D ) {
NodePtr_t
NPtr ;
intdequeue( NodePtr_t * DQP, Data_t * Dptr
){
NodePtr_t tempPtr ;
NPtr = malloc( sizeof( Node_t ) ) ;
Data_t D ;
if( NPtr == NULL ) return NULL ;

NPtr->NextPtr
if( *DQP == NULL ) return 0 ; \\ Stack is
empty so fail= NULL ;
The basic queue is a singly linked list with two
pointers, Head and Tail
There are two fundamental operations
 enqueue() – insert a node at the Tail position
}
Copy( payload
NPtr->Data,
Copy( (*DQP)->Data, Dptr ) ; \\ Copy-return
dataD ) ;
 dequeue()
– obtain
from the
tempPtr
= *DQP ;
\\ Getpayload
address ofdata
next node
if(stack
*NQP
!=node
NULL )
*DQPHead
= (*DQP)->NextPtr
\\ Update
pointer
position,; then
delete
the
= *NQP ;
free( tempPtr ) ;
\\ DeallocateNPtr->NextPtr
node
*NQP = NPtr ;
return
NPtr ;
return 1 ;
\\ Success
is TRUE
}
node at the
TailPtr
Enqueue
Pointer
HeadPtr
Pointer
Dequeue
Data Nxt
Data Nxt
Data
0
Queues
 There are different kinds of queues
 Circular Queues are singly linked lists with only a
single named pointer, sometimes called CQptr
 All enqueue and dequeue operations are performed using
CQptr. (CQptr == NULL indicates an empty queue.)
 A further distinction is that the last node points to the first node –
the NextPtr field is never NULL!
 Not necessarily FIFO
 Sometimes called Round-Robin queue
 Used for print spoolers, concurrency handling and many other
applications
Dequeue
Enqueue
CQptr
Pointer
Data Nxt
Data Nxt
Data Nxt
Advanced data structure abstractions
Exploring the abstract connections between dynamically
allocated data structures and designing efficient
algorithms for ADTs
I think that I shall never see,
A program lovelier than a Tree …
- with apologies to Joyce Kilmer
RootPtr
Data Nxt
Ptr
Data Nxt
Data
RootPtr
Ptr
Data L R
Data L R
Data L R
Data L R
Data L R
Data L R
Data L R
Data L R
0
Binary Trees
the is
ideal
case structure
of N = 2K nodes
with
perfecton a
 A binary In
tree
a data
that is
based
balancing of Left and Right child nodes, there is:
specific relationship that exists between two neighbour
1 root node – level-1
nodes
2 level-2 nodes
 Example: P1->Data.ID is less than P2->Data.ID
4 level-3 nodes, and so on, up to
log2(N/2) level-(K-1) nodes.
 Each node contains
two pointer fields
 A Left child pointer
Recall that log (N/2) = K-1.
 A Right child pointer 2
For N=1024 nodes there are only K=10 levels.
 This
implies
for (Right)
orderedchild
nodes,
a binary
 Nodes that
do not
havethat
a Left
assign
NULL values to
search
that pointer
field strategy can be implemented.
 When both node pointers are NULL, the node is called a Leaf
node.
struct DataRec {
int SID ;
char Lname[30] ;
char Fname[20] ;
float GPA ;
}
typedef struct DataRec Data ;
A Binary Tree
RootPtr
Ptr
struct BinTreeRec {
Data D ;
struct BinTreeRec * Left ;
struct BinTreeRec * Right ;
}
Root node
Data L R
Left child
Data L R
Data L R
Left child
Data L R
Leaf
Right child
Data L R
Leaf
Right child
Data L R
Left child
Data L R
Leaf
Right child
Data L R
Leaf
Tree Constructions
10
 Constructing a tree is done by inserting each new
node at a leaf position
20
 We assume the Left Child is less than the Right Child.
 Consider three different input orders
30
 10, 20, 30, 40, 50, 60, 70
 20, 50, 30, 40, 10, 60, 70
40
 40, 20, 10, 30, 60, 50, 70
50
 This produces a highly unbalanced
tree – it is actually a singly linked list
with wasted left children! Only linear
search can be applied.
60
70
Tree Constructions
 Constructing a tree is done by inserting each new
node at a leaf position
 We assume the Left Child is less than20the Right Child.
 Consider three different input orders
 10, 20, 30, 40, 50, 60, 70
10
50
 20, 50, 30, 40, 10, 60, 70
 40, 20, 10, 30, 60, 50, 70
 This version is better
balanced, but search is
between O(n) and O(log n)
30
60
40
70
Tree Constructions
 Constructing a tree is done by inserting each new
40
node at a leaf position
 We assume the Left Child is less than the Right Child.
20
60
 Consider three different input orders10, 20, 30, 40, 50,
60, 70
 20, 50, 30, 40, 10, 60, 70
 40, 20, 10, 30, 60, 50, 70
 This version is perfectly balanced
and search is O(log n)
10
30
50
70
Tree Traversal Techniques
 Traversals
 Inorder
 Preorder
 Postorder
40
60
20
10
5
30
15
25
50
35
45
70
55
65
75
Tree Traversal Techniques
inOrder:
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75
 Traversals
void inOrder ( TreeNodePtr_t TPtr ) {
 Inorder
if( TPtr != NULL ) {
inOrder( TPtr->leftChild ) ; \\ First, go left
outputNode( TPtr ) ;
\\ output node
inOrder( TPtr->rightChild
) ; \\ then go right
40
}
 Preorder
 Postorder
20 ;
return
60
}
10
5
30
15
25
50
35
45
70
55
65
75
preOrder:
40, 20, 10,
5, 15, 30, 25, 35, 60, 50, 45, 55, 70, 65, 75
Tree Traversal Techniques
 Traversals
void preOrder ( TreeNodePtr_t TPtr ) {
 Inorder
if( TPtr != NULL ) {
outputNode( TPtr ) ;
\\ output node
preOrder( TPtr->leftChild ) ; \\ then, go left
preOrder( TPtr->rightChild
) ; \\ then go right
40
}
 Preorder
 Postorder
20 ;
return
60
}
10
5
30
15
25
50
35
45
70
55
65
75
postOrder:
5, 15, 10, 25, 35, 30, 20, 45, 55, 50, 65, 75, 70, 60, 40
Tree Traversal Techniques
 Traversals
void postOrder ( TreeNodePtr_t TPtr ) {
 Inorder
if( TPtr != NULL ) {
postOrder( TPtr->leftChild ) ; \\ First, go left
postOrder( TPtr->rightChild ) ; \\ then go right
outputNode( TPtr
\\ output node
40 ) ;
}
 Preorder
 Postorder
return20;
60
}
10
5
30
15
25
50
35
45
70
55
65
75
Tree Traversal Techniques
inOrder:
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75
Traversals
40, 20,

preOrder:
10,
5, 15, 30, 25, 35, 60, 50, 45, 55, 70, 65, 75
 Inorder
postOrder:
5, 15, 10, 25, 35, 30, 20, 45, 55, 50, 65, 75, 70, 60, 40
 Preorder
 Postorder
40
60
20
10
5
30
15
25
50
35
45
70
55
65
75
Tree Data Structures
 There are several important algorithms necessary to
work with tree data structures, including:
 InsertTreeNode
 DeleteTreeNode
 RotateNodeLeft – used to reorder parent-child node relationships
 RotateNodeRight
 FindTreeHeight
 This subject is covered in much more detail in 2nd year
courses on data structures and advanced programming
Advanced Tree Data Structures
 In order to maintain a balanced tree, Adelson-Velskii
and Landis developed the tree balancing algorithm
leading to AVL trees.
 Youtube presentation:
http://www.youtube.com/watch?v=5C8bLQBjcDI
 Closely related to AVL trees are Red-Black trees
 Often, trees have more than 2 children
 4 children – Quad-Trees (used in 2D graphics)
 8 children – Oct-Trees (used in 3D graphics)
Advanced Data Structures - Graphs
 In closing we mention the structure called a Graph.
 Graphs are noteworthy due to the properties:
 There may be more than one entry pointer to the graph
 Each graph node may point to multiple nodes
 There is no concept of level – there is a notion of traversal
distance, however
 It is possible to traverse a graph such that a node is visited more
than once
 Application – Natural Language Problems (NLP)
 When select nodes contain clusters of child nodes and
primary links are between these select nodes, the
structure is called a network graph.
 Graphs and networks are often used in Queueing Theory
 Applied to problems in manufacturing, process control
Advanced Data Structures - Graphs
 A quick video introduction by Dickson Tsai (8+ minutes)
 https://www.youtube.com/watch?v=vfCo5A4HGKc
 Graph Theory: An Introduction by patrickJMT (12+ minutes)
 https://www.youtube.com/watch?v=HmQR8Xy9DeM
 A longer lecture by Jonathan Shewchuk of UCBerkeley (50+
minutes)
 https://www.youtube.com/watch?v=ylWAB6CMYiY
Summary
Advanced data structures: self-referential data structures, dynamic
memory allocation, linked lists, stacks, queues, trees
Topic Summary
 Self-referential data structures
 Dynamic memory allocation
 Linked lists
 Single and Double linkage
 Stacks
Study examples –
Adapt them to your
own uses !
 Queues
 Trees
 Study – Chapter 12: Data Structures
 Abstract data structures, dynamic memory allocation, using pointers and
self-referential data structures, linked lists, stacks and queues.
 Review all Chapters covered
 Preparation for the Final Examination.