CISC 2200 Lecture Notes - Lecture 4: Linked List, Linear Search, The Algorithm

0 views3 pages
user avatar
Published on 4 Jul 2020
School
Fordham University
Department
Computer and Information Sciences
Course
CISC 2200
Professor
Pointer Review
Example
Int a = 10;
Int *ip = &a;
Cout << “*IP:” << *IP << “ a =” << a << endl;
// *ip would be 1000 (address of a)
//
Int **ip2 = &ip;
Int b = 100;
*ip2 = &b;
*ip = 100;
Cout << “*ip: “ << *ip << “ a =” << A << “b=” << b << endl;
//*ip would be the address of b
//b will be 99
//a will stay as 10
int**& pr = ip;
Pr = &a;
*pr = 200;
// pr will be ip in a sense
//a will become 200
UnsortedType as a Linked List
Linked List : A collection of nodes that are linked together in a chain using pointers
Node: The basic component of a linked list; stores data and a pointer to the next node
Nodes are created when needed using dynamically allocated memory
The last node in the list has a NULL pointer.
We can use a struct for nodes and list types to be together
Struct NodeType
{
ItemType info;
NodeType* next;
};
NodeType* node = new NodeType;
Node -> info = type;
Node -> next = null;
ListData = node;
PutItem
When the list is empty, PutItem creates a node and sets the external pointer listData to
it.
1. Create a new node
2. Set the node’s info to the input data
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Cout << *ip: << *ip << a = << a << endl; // *ip would be 1000 (address of a) Cout << *ip: << *ip << a = << a << b= << b << endl; //a will stay as 10 int**& pr = ip; // pr will be ip in a sense. We can use a struct for nodes and list types to be together. Putitem: when the list is empty, putitem creates a node and sets the external pointer listdata to it, 1. Set the node"s info to the input data: 3. Set the node"s next pointer to the listdata, the first item in the list: 4. Set listdata to point to the new node (this order matters) Node -> next = listdata; listdata = node; length++: the algorithm is unchanged: linear search through the list to find the desired item. In fact, the implementation is largely unchanged; it just needs to use pointers instead of array indices.