Data Structures in C

Question 1

Linked Structures

Answer 1

• Two approaches to keeping data organized:
  – Pack values consecutively, in the same region of memory: an array or a struct.
  – Use pointers to make connections between different data items: a linked structure
• A linked list is a basic linked structure
  – With each node holding a value …
  – … and a pointer to the next node

Question 2

Linked Structure Tradeoffs

Answer 2

• Compared to arrays, linked structures offer
  certain tradeoffs
  – Easier to grow the structure a little bit at a time
  – Don’t need to find large, contiguous regions of memory
  – Can come up with some creative ways to organize the structure, well suited to certain operations
• Linked lists, balanced trees, disjoint sets, tries …
  – Locality may be worse, jumping all over memory
  – Need to traverse links, instead of using pointer arithmetic to go right where we need to

Question 3

Buildng a Linked List in C

Answer 3

• We can use a struct to represent a node.
  struct NodeStruct {
  int value; -> value in a node
  struct NodeStruct *next;
  }; -> pointer to the next node
  typedef struct NodeStruct Node; -> short name to call the node by
  Node *head = NULL;

Question 4

Adding to a List

Answer 4

• We can use dynamic memory allocation to get space for each node.
  Node *n = (Node *)malloc( sizeof( Node ) ); -> get space for a node
  n->value = val; -> Store a value in it
  n->next = head; -> Link it in at the front
  head = n;
• We could allocate a bunch of nodes statically
  – but dynamic allocation lets us grow the list as big as we need.

Question 5

Traversing a List

Answer 5

• In C, a NULL pointer evaluates to false
• We can use this to write some very simple
  traversal code
  for ( Node *n = head; n; n = n->next )
  printf( “%d\n”, n->value);
  Node *n = head : start at the head
  n :While the current node is non-NULL
  n->next : Move to the next node.

Question 6

Organizing our List Code

Answer 6

• We’d like to organize our code
  – Instead of putting linked list code all over the place
  – We’d like organize list operations into reusable functions
• For example:
  Node *head = NULL; :Here’s our list, a global
  pointer.
  void addValue( int val ) : A function to add a
  new value.
  {
  Node *n = (Node *)malloc( sizeof( Node ) );
  n->value = val;
  n->next = head;
  head = n;
  }

Question 7

Reusable Traversal Implementation

Answer 7

• We can use the visitor design pattern to make
  a reusable traversal function.
  void traverse( void (*visit)( int val ) )
  {
  for ( Node *n = head; n; n = n->next )
  visit( n->value );
  }
  *visit -> Pass me the function you
  want to call on each value.
  visit(n->value) -> call the visit function for each value
• Here’s a visitor function to print each value.
  static void myVisitor( int val )
  {
  printf( “%d\n”, val ); -> I print each value, without
  needing to know how the list is
  organized.

}
* Here’s how to use the traversal function.
traverse( myVisitor );->This gives the address of the
myVisitor() function.
use static most of the time to not pollute global namespace

Question 8

Organizing Our List Code(New Way)

Answer 8

• This organization has some disadvantages.
  – We store the list as a global
  – So, we can only have one list, the global one.
• To support multiple, independent lists, we’ll need to be more creative.
  Node *head = NULL;
  void addValue( int val )
  {
  Node *n = (Node *)malloc( sizeof( Node ) );
  n->value = val;
  n->next = head;
  head = n;
  }
• How about this? We pass in the list as a
  parameter
  void addValue( Node *head, int val )
  {
  Node *n = (Node *)malloc( sizeof( Node ) );
  n->value = val;
  n->next = head;
  head = n;
  }
  Node *myList = NULL;
  …;
  addValue( myList, 75 );
  myList is unchanged since copy is passed and there is leaked memory
• One solution, return the new head pointer
  Node *addValue( Node *head, int val )
  {
  Node *n = (Node *)malloc( sizeof( Node ) );
  n->value = val;
  n->next = head;
  return n; -> Here’s the new head of the list
  }
  Node *myList = NULL;
  …;
  myList = addValue( myList, 75 ); -> be sure to update your head pointer
• Or, we could pass the head by reference, so
  the function could change it.
  – That’s a pointer to a pointer to a Node
  void addValue( Node **headPtr, int val )
  {
  Node *n = (Node *)malloc( sizeof( Node ) );
  n->value = val;
  n->next = *headPtr;
  *headPtr = n;
  }
  Node *myList = NULL;
  …;
  addValue( &myList, 75 );
• Or, more typically, we could make a little
  structure representing the list itself
  typedef struct { -> I represent a whole list
  Node *head; -> Here’s the head pointer.
  -> Plenty of room for more
  fields if you need them
  (e.g., a tail pointer)
  } List;
• We just need to pass a pointer to this struct to every function that uses a list.
  void addValue( List *list, int val )
  {
  Node *n = (Node *)malloc( sizeof( Node ) );
  n->value = val;
  n->next = list->head;
  list->head = n;
  }
  List myList = { NULL };
  …;
  addValue( &myList, 75 );
• A pointer to a List struct lets a function:
  – Read fields related to the list
  – Or, modify the list if needed

Question 9

Faking Object Orientation

Answer 9

• We could use this to simulate object-orientation
• Instead of member functions we could
  – Define a bunch of (free) functions
  – Pass in a pointer to the object (struct) these functions are supposed to work on.
• Surprise! This is how Java and C++ work internally

Question 10

Freeing Lists

Answer 10

Don’t do this!
* Eventually, we have to free the memory for
our linked list
* Here’s a bad way to do it:
for ( Node *n = head; n; n = n->next )
free( n );
(n->next in for loop )-> didn’t you just free that node?
* This tries to use a node, right after we free it.
Correct Way!
while ( head ) {
Node *next = head->next;
free( head );
head = next;
}

Question 11

Removing Node

Answer 11

• To remove a node
  – We might choose to handle the head of the list as a special case
  – Then nodes later in the list if it’s not the head node.
  if ( head ) {
  if ( head->value == val ) { -> Is the target value in the first node?
  Node *n = head;
  head = head->next; -> If so, unlink and free it.
  free( n );
  }
  …
  (for node that is not the head)
  Node *pred = head;
  while ( pred->next && pred->next->value != val ) -> Look for the predecessor node, the one before the one you want to remove
  pred = pred->next;
  if ( pred->next ) {
  Node *n = pred->next;
  pred->next = pred->next->next;
  free( n );
  }
  }

Question 12

Getting Creative

Answer 12

• How about this technique
  bool removeValue( List *list, int val )
  {
  Node *target = list->head;
  while (target &&
  target->value != val)
  target = target->next;
  if ( target ) {
  Node *n = target;
  target = target->next; -> wrong
  free( n );
  return true;
  }
  return false;
  }

Question 13

Pointer to Node

Answer 13

• We know how to make a pointer to a node:
  Node *target;
• It’s good for … well … keeping up with a node
• You can easily get to the fields of that node
  target ->value
  target -> next

Question 14

Pointer to a Pointer to a Node

Answer 14

• A pointer to a node won’t let you remove the
  node itself.
• But, a pointer to a pointer, that’s something
  more useful:
  Node **target;
• A dereference will still give us a pointer to a
  node
• We can use this to access fields of the node:
  (target)->val
  (target)->next
• You can use this pointer to change links in the list.
• You could change a link inside a node:
• Or, you could change the head pointer itself.

Question 15

Traversing via Pointer to Pointers

Answer 15

• Traversing the list requires moving to the next pointer inside the current node.
  Get the pointer inside the current node. ->
  (target)->next
  Make its address the new target. -> target = &((target)->next);

Question 16

Removing Nodes(Simplified)

Answer 16

• To remove a node, we must change the pointer that points to it.
  – Every node has one such pointer
  – Either the pointer inside its predecessor.
  – Or, the head pointer itself.
• Both of these pointer have the same type (pointer to Node)
• We can handle them uniformly via a pointer to pointer to
  Node.
• We’ll start with a pointer pointing to the head pointer:
• As we traverse the list, we will move the ahead to
  pointers within the nodes.
  – This will give us a way to remove the next node on the
  list.
  Pic on Doc

Question 17

Removing Nodes(Simplified Code)

Answer 17

bool removeValue( List list, int val )
{
Node **target = &list->head;
while ( target && (target)->value != val )
target = &(target)->next;
if ( *target ) {
Node *n = *target;
target = (target)->next;
free( n );
return true;
}
return false;
}

Question 18

Binary Search Trees

Answer 18

• A linked list is good for some things
  – A stack, a queue or a short list.
• Alternative organizations can give better
  performance for other operations.
• Like a Binary Search Tree
  – Every node has two pointers
  – Values (keys) are organized based on comparison
• Each comparison splits the set of values into two smaller subsets.
  – Ideally, each about the same size.
• Each time we traverse a node
  – we eliminate about half the
  keys.

Question 19

Building a BST

Answer 19

• We can represent the nodes of a BST as
  structs.
  struct NodeStruct {
  int key;
  struct NodeStruct *left, *right;
  };
  typedef struct NodeStruct Node; -> Short name for node structure
• And, we can have a struct for the whole tree.
  typedef struct {
  Node *root;
  } Tree;
  To see example tree and traversal see doc
• To find a value, you start at the root.
• Then descend left or right.

Question 20

Finding a Value

Answer 20

bool containsKey( Tree *tree, int val )
{
Node *n = tree->root;
while ( n ) {
if ( n->key == val )
return true;
if ( val < n->key )
n = n->left;
else
n = n->right;
}

return false;
}

Question 21

Tree Traversal(Code)

Answer 21

• It’s easy to traverse the tree recursively.
• This gives us the keys in sorted order.
  void printKeys( Node *n )
  {
  if ( n ) {
  printKeys( n->left );
  printf( “%d “, n->key );
  printKeys( n->right );
  }
  }

Question 22

Generic Tree Traversal

Answer 22

• We can offer a generic traversal interface with
  a visitor function called on each key.
  void traverse( Node n, void (visit)( int val ) )
  {
  if ( n ) {
  traverse( n->left, visit );
  visit( n->key );
  traverse( n->right, visit );
  }
  }
  We can call it like:
  traverse( tree.root, myVisitor );
  Same visitor function as the linked-list example.