Linked List

<aside> 💡 A linked list is a linear data structure in which elements are stored in nodes, each consisting of a value and a reference to the next node.

</aside>

struct llnode {
  int item;
  struct llnode *next;
};

struct llist {
  struct llnode *front;
};

// list_create() creates a new, empty list
// effects: allocates memory: call list_destroy
struct llist *list_create(void) {
  struct llist *lst = malloc(sizeof(struct llist));
  lst->front = NULL;
  return lst;
}

// add_front(i, lst) adds i to the front of lst
// effects: modifies lst
void add_front(int i, struct llist *lst) {
  struct llnode *newnode = malloc(sizeof(struct llnode));
  newnode->item = i;
  newnode->next = lst->front;
  lst->front = newnode;
}

// insert(i, slst) inserts i into sorted list slst
// requires: slst is sorted [not asserted]
// effects:  modifies slst
// time:     O(n), where n is the length of slst

void insert(int i, struct llist *slst) {
  if (slst->front == NULL || i < slst->front->item) {
    add_front(i, slst);
  } else {
    // find the node that will be "before" our insert
    struct llnode *before = slst->front;
    while (before->next && i > before->next->item) {
      before = before->next;
    }
    // now do the insert
    struct llnode *newnode = malloc(sizeof(struct llnode)); 
    newnode->item = i;
    newnode->next = before->next;
    before->next = newnode;
  }
}

void free_nodes(struct llnode *node) {
  if (node) {
    free_nodes(node->next);
    free(node);
  }
}

void list_destroy(struct llist *lst) {
  free_nodes(lst->front);
  free(lst);
}

(There’s a lot more functionalities you might want to review…)


Queue ADT

Stack → LIFO Queue → FIFO

struct llnode {
  int item;
  struct llnode *next;
};

struct queue {
  struct llnode *front;
  struct llnode *back;    // <--- NEW
};

Tree ADT

At the implementation level, trees are very similar to linked lists. However, each node can link to more than one node

Untitled

struct bstnode {
    int item;
    struct bstnode *left;
    struct bstnode *right;
    int count;              // *****NEW
};

Dictionary and Graph ADTs

<aside> 💡 The dictionary ADT (also called a map, associative array, key-value store or symbol table), is a collection of pairs of keys and values.

</aside>

struct bstnode {
  int item;                // key
  char *value;             // additional value (augmentation)
  struct bstnode *left;
  struct bstnode *right;
};

struct dictionary {
  struct bstnode *root;
};

(I don’t think we’ll be working with graphs in this course.. )

https://online.cs.uwaterloo.ca/assets/courseware/v1/64fda2c92298b032bc18287d467d161c/asset-v1:UW+CS136+2023_01+type@asset+block/10-linked-data-show.pdf