Lecture Preview: Pointers and Linked Nodes

(Suggested book reading: Programming Abstractions in C++, 12.2 - 12.3; 14.3)

Today we will learn about a C++ feature called pointers. A pointer stores the memory address of another value. Get the address of an existing value by preceding it with & . Declare a pointer by following a data type with * . You can also follow a pointer to the memory address at which it points by preceding its name with * . Here is a brief example:

int x = 42;
int* p = &x;
cout <<  p << endl;   // 0x7f8e20
cout << *p << endl;   // 42
*p = 99;
cout << x << endl;    // 99

We can use pointers to create a collection called a linked list. A linked list is like a Vector or ArrayList, but instead of storing its elements in one large array block of data, it stores each element in a small object called a node. Nodes are linked together by having each node store a pointer that remembers the memory address of the next node that follows it. Here is an example structure for representing a node:

struct ListNode {
    int data;
    ListNode* next;
};

You could use this structure in the following way to create a simple list of elements of data:

ListNode* list = new ListNode();
list->data = 10;

list->next = new ListNode();
list->next->data = 20;

list->next->next = new ListNode();
list->next->next->data = 30;
list->next->next->next = NULL;

This would produce the following list:

linked nodes

We use the special value NULL to indicate the end of the list. NULL is a special value in C++ representing a pointer to nothing; it indicates the lack of any further data.

This document and its content are copyright © Marty Stepp, 2015. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.