Showing 1 out of 3
17 - Linked Lists I.pdf-CPSC 260 Li...
Page 1
CPSC 260
Slide 1
Using dynamic memory allocation we can specify the
capacity of an
IntVector
at run-time
It is expensive
to increase the capacity of the
IntVector
:
allocate
memory to a larger array
copy
the data from the original array to the new array
release
the memory allocated to the original array
It is not
possible to increase the capacity of the original
array
will allow us to store data in a structure that can
grow or shrink dynamically as needed
CPSC 260
Slide 2
A singly linked list is a linear
, sequential access
,
homogeneous
data structure
Domain
: a collection of nodes
each of which contains a data
element; a pointer to a node at the head
of the list
Structure
: there is a pointer to the first node
in the list and
each node contains a pointer that points to the next node
in
the list, with the exception of the last
item1
item2
item3
item4
CPSC 260
Slide 3
Operations
:
insertFirst, insertLast, insertAfter
find
deleteItem
printNode . . . not an exhaustive list
We will now implement a linked list toolkit – a module that
contains the implementation of the operations that we want
to support. In so doing, we are implementing the linked list
as a concrete data type
.
First we must determine how to represent a node. This is a
simple data structure so we will implement it as a CDT using
a
struct
. We will assume that a
typedef
statement is used
to define the data type of the elements to be stored in the
list:
typedef int Item_type;
CPSC 260
Slide 4
typedef int Item_type;
struct Node
{
Item_type item;
Node* next;
};
Now let’s suppose that we declare a pointer to a
Node
object and dynamically allocate memory to a new node:
Node* nodePtr;
nodePtr = new Node;
Recall that we can now access the individual elements within
the node in two ways:
(*nodePtr).item = 2;
nodePtr->next = NULL;
nodePtr
2
nodePtr
?
?
CPSC 260
Slide 5
When we insert a new element into a linked list, we need to
create a new node. We will start by writing a helper
function to do this:
Node* makeNode( const Item_type& theItem,
Node* nextNode = 0 )
//Post: a new node is created containing theItem; the
//new node is linked to nextNode (or is null); a
//pointer to the new node is returned
{
Node* newNode = new Node;
newNode->item = theItem;
newNode->next = nextNode;
return newNode;
}
Note that in our documentation, we do not specify what will
happen if our request for a new node fails due to insufficient
memory. We will address this problem later in the course.
CPSC 260
Slide 6
A note on formal parameter names
The following variant also works:
Node* makeNode( const Item_type& item ,
Node* nextNode = 0 )
//Post: a new node is created containing theItem; the
//new node is linked to nextNode (or is null); a
//pointer to the new node is returned
{
Node* newNode = new Node;
newNode-> item = item ;
newNode->next = nextNode;
return newNode;
}
In this case the compiler knows which is which:
the first
item
is a field name in a
Node
struct
the second
item
is the formal parameter

Browse thousands of Study Materials & Solutions from your Favorite Schools
UBC Vancouver
UBC_Vancouver
School:
Object-Oriented_Programming
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades