Editing Pointer (computer programming) (section)

===Use in data structures===
When setting up [[data structure]]s like [[List (computing)|lists]], [[Queue (abstract data type)|queues]] and trees, it is necessary to have pointers to help manage how the structure is implemented and controlled. Typical examples of pointers are start pointers, end pointers, and [[Stack (abstract data type)|stack]] pointers. These pointers can either be '''absolute''' (the actual [[physical address]] or a [[virtual address]] in [[virtual memory]]) or '''relative''' (an [[offset (computer science)|offset]] from an absolute start address ("base") that typically uses fewer bits than a full address, but will usually require one additional arithmetic operation to resolve).

Relative addresses are a form of manual [[memory segmentation]], and share many of its advantages and disadvantages. A two-byte offset, containing a 16-bit, unsigned integer, can be used to provide relative addressing for up to 64 [[kibibytes|KiB]] (2<sup>16</sup> bytes) of a data structure. This can easily be extended to 128, 256 or 512 KiB if the address pointed to is forced to be [[Data structure alignment|aligned]] on a half-word, word or double-word boundary (but, requiring an additional "shift left" [[bitwise operation]]—by 1, 2 or 3 bits—in order to adjust the offset by a factor of 2, 4 or 8, before its addition to the base address). Generally, though, such schemes are a lot of trouble, and for convenience to the programmer absolute addresses (and underlying that, a ''[[flat address space]]'') is preferred.

A one byte offset, such as the hexadecimal [[ASCII]] value of a character (e.g. X'29') can be used to point to an alternative integer value (or index) in an array (e.g., X'01'). In this way, characters can be very efficiently translated from '[[raw data]]' to a usable sequential [[Array data structure|index]] and then to an absolute address without a [[lookup table]].

====C arrays====
In C, array indexing is formally defined in terms of pointer arithmetic; that is, the language specification requires that <code>array[i]</code> be equivalent to <code>*(array + i)</code>.<ref name="Plauger1992">{{cite book |title=ANSI and ISO Standard C Programmer's Reference |last=Plauger |first=P J |author-link=P. J. Plauger |author2=Brodie, Jim |year=1992 |publisher=Microsoft Press |location=Redmond, WA |isbn=978-1-55615-359-4 |pages=[https://archive.org/details/ansiisostandardc00plau/page/108 108, 51] |quote=An array type does not contain additional holes because all other types pack tightly when composed into arrays ''[at page 51]'' |url-access=registration |url=https://archive.org/details/ansiisostandardc00plau/page/108}}</ref> Thus in C, arrays can be thought of as pointers to consecutive areas of memory (with no gaps),<ref name="Plauger1992" /> and the syntax for accessing arrays is identical for that which can be used to dereference pointers. For example, an array <code>array</code> can be declared and used in the following manner:

<syntaxhighlight lang="c">
int array[5];      /* Declares 5 contiguous integers */
int *ptr = array;  /* Arrays can be used as pointers */
ptr[0] = 1;        /* Pointers can be indexed with array syntax */
*(array + 1) = 2;  /* Arrays can be dereferenced with pointer syntax */
*(1 + array) = 2;  /* Pointer addition is commutative */
2[array] = 4;      /* Subscript operator is commutative */
</syntaxhighlight>

This allocates a block of five integers and names the block <code>array</code>, which acts as a pointer to the block. Another common use of pointers is to point to dynamically allocated memory from [[malloc]] which returns a consecutive block of memory of no less than the requested size that can be used as an array.

While most operators on arrays and pointers are equivalent, the result of the <code>[[Sizeof#Using sizeof with arrays|sizeof]]</code> operator differs. In this example, <code>sizeof(array)</code> will evaluate to <code>5*sizeof(int)</code> (the size of the array), while <code>sizeof(ptr)</code> will evaluate to <code>sizeof(int*)</code>, the size of the pointer itself.

Default values of an array can be declared like:

<syntaxhighlight lang="C">
int array[5] = {2, 4, 3, 1, 5};
</syntaxhighlight>

If <code>array</code> is located in memory starting at address 0x1000 on a 32-bit [[Endianness#Little-endian|little-endian]] machine then memory will contain the following (values are in [[hexadecimal]], like the addresses):

:{| class="wikitable" style="font-family:monospace;"
|-
|  
! 0 || 1 || 2 || 3
|-
! 1000 
| 2 || 0 || 0 || 0
|-
! 1004 
| 4 || 0 || 0 || 0
|-
! 1008 
| 3 || 0 || 0 || 0
|-
! 100C 
| 1 || 0 || 0 || 0
|-
! 1010 
| 5 || 0 || 0 || 0
|}
Represented here are five integers: 2, 4, 3, 1, and 5. These five integers occupy 32 bits (4 bytes) each with the least-significant byte stored first (this is a little-endian [[CPU architecture]]) and are stored consecutively starting at address 0x1000.

The syntax for C with pointers is:
* <code>array</code> means 0x1000;
* <code>array + 1</code> means 0x1004: the "+ 1" means to add the size of 1 <code>int</code>, which is 4 bytes;
* <code>*array</code> means to dereference the contents of <code>array</code>. Considering the contents as a memory address (0x1000), look up the value at that location (0x0002);
* <code>array[i]</code> means element number <code>i</code>, 0-based, of <code>array</code> which is translated into <code>*(array + i)</code>.

The last example is how to access the contents of <code>array</code>. Breaking it down:
* <code>array + i</code> is the memory location of the (i)<sup>th</sup> element of <code>array</code>, starting at i=0;
* <code>*(array + i)</code> takes that memory address and dereferences it to access the value.

====C linked list====
Below is an example definition of a [[linked list]] in C.

<syntaxhighlight lang="C">
/* the empty linked list is represented by NULL
 * or some other sentinel value */
#define EMPTY_LIST  NULL

struct link {
    void        *data;  /* data of this link */
    struct link *next;  /* next link; EMPTY_LIST if there is none */
};
</syntaxhighlight>

This pointer-recursive definition is essentially the same as the reference-recursive definition from the language [[Haskell]]:

<syntaxhighlight lang="haskell">
 data Link a = Nil
             | Cons a (Link a)
</syntaxhighlight>
<code>Nil</code> is the empty list, and <code>Cons a (Link a)</code> is a [[cons]] cell of type <code>a</code> with another link also of type <code>a</code>.

The definition with references, however, is type-checked and does not use potentially confusing signal values. For this reason, data structures in C are usually dealt with via [[wrapper function]]s, which are carefully checked for correctness.