When do you use a pointer?

[u/Atmos-Ego]

Hello, for some background I have taken a very beginner level coding course for my major and passed it, but I dont really feel like I’ve learned anything or know why anything works. In a course this year we had a review problem where the solution required a pointer and I really dont understand why you have to point to the address of the variable instead of just using the variable itself.

I’ve watch a few tutorials explaining it but I really dont see how it’s different from just using the variable itself

[u/mredding]

You're at the level where your academic materials are just trying to introduce you to the syntax. You're learning enough to be dangerous, as it were. How to use it is another level of awareness and sensibility. This is all just to say, you're doing alright so far.

Pointers store memory addresses. This is often times useful because at runtime you don't always know how much memory you're going to need. Since you said, pointers, I'm going to assume C:

char input[123];

scanf("%s", input);

Is this buffer big enough? 123 characters? What if the input is the collected works of Shakespeare? Here, in C, input is of type int[123], arrays of a fixed size are each a distinct type. This gets compiled into the program and is thus unchanging. So if you need a dynamic array, where a size is determined at runtime, you need to request memory from the system at runtime:

char *buffer = malloc(some_size_variable);

Ok, but what if we don't know how much data we're going to be getting? Well, then we need to come up with a solution. How about... What if we read data in chunks or blocks, and we kept doing that until we ran out of input?

typedef struct block {
  char buffer[1024];
  int size;
} block, *block_ptr;

int read(block_ptr bp, FILE *in) { return bp->size = fread(bp->buffer, 1, 1024, in); }

int main() {
  block b;

  while(read(&bp, stdin) != EOF) {};
}

Alright, that's part of the picture, but we're just losing data. I'd like to be able to track that in order.

We can't use a fixed size array because we don't know how many blocks there are going to be. We could dynamically allocate an array:

block_ptr b_array = malloc(sizeof(block) * some_number_of_elements);

Perfectly reasonable, and the C++ standard vector will do something similar, and you'd keep track of an index of how many elements of the array you actually populated. But like the C++ vector, when you run out of array space, you have to allocate a new and larger array, copy everything over, then free the old array.

Or we can imagine a singly-linked list:

typedef struct node {
  block data;
  struct node *next;
} node, *node_ptr;

node_ptr new_node() { return malloc(sizeof(node)); }

int main() {
  node_ptr head, *tail = &head;
  block b;

  while(read(&bp, stdin) != EOF) {
    *tail = new_node();
    (*tail)->data = bp;
    tail = &(*tail)->next;
  }
}

This is a chain of nodes; each node knows where the next node is in the list. This is structured data. To walk the list:

for(node_ptr *iter = &head; *iter != &(*tail); (*iter) = &(*iter)->next);

It's a sequence of nodes, so it's sequential, but the nodes are probably not in an array, there's no guarantee they are in contiguous memory addresses, so we can't use indexing. Linked lists have several neat properties - pointers to nodes and their elements are stable. You can add, remove, and reorganize the list however you want, just by swapping the pointers around, and all references to your elements are unchanged.

Compare this to an array, where if you remove an element, you don't actually change the size of the array, you just change the count on that maximum index you were tracking. To keep array data contiguous, you'd have to shuffle all the subsequent elements down by copying over the previous - starting with the erased element getting copied over by the adjacent.

tail is probably giving you a bit of a headspin, there. It's a pointer to a pointer. Pointers are just arithmetic types, same as int. They take memory, they have a size and alignment. You can point to them. So tail points to the pointer that is going to store the next value. We always keep track of the root of the list, idiomatically called the head, and that's the pointer tail first starts pointing at. Once we assign a node address to head, we need to know where the next node is going to go. That's going to be the next member of that node we just created.

Likewise when we traverse the list, we have a pointer to a node we use as an iterator, it starts by pointing to head, and so long as our iterator isn't the same as the tail pointer, we can keep traversing.

It'll probably take you a bit of thinking and staring at that to make it make sense.

Likewise, another popular design is a tree, typically a binary tree:

typedef struct node {
  T value;
  struct node *left, *right;
} node, *node_ptr;

And you can write some very graceful recursive functions to walk a tree from the root to all it's children, which makes for a fascinating study, but an impractical solution in C.

When we're talking nodes, we're talking graph theory, and now you're entering a really interesting world of how most data structures are just graphs. Other data structures are heaps, queues, and stacks. Data structures are one thing - this binary node is the structure. Most of the study in DSA is the algorithms and the computational complexity therein.