Abstract Data Types

Stack

• last item added is the first one to be removed
• Elements are added and removed from the top of the stack.
• Common operations: push (add), pop (remove)

Queue

• first item added is first one to be removed
• Elements are added at the rear (enqueue) and removed from the front (dequeue) of the queue.
• Common Operation: enqueue, dequeue
• Used for algorithms like breadth-first traversal of graphs

Priority Queue

• stores elements along with associated priorities
• Elements with higher priority are dequeued before those with lower priority.
• Common operations: insert (enqueue), delete (dequeue the highest priority element)
• Used for algorithms like Dijkstra's shortest path, Prim's algorithm for minimum spanning tree

if head 1 == NULL return head2;

if head2 == NULL return head1;

malloc a newHead

if head1->data <= head2->data

newHead = head1

head1 move to next

else

newHead = head2

head2 move to next

a new temp head node = head

while head1 is not NULL && head2 is not NULL

node swap = NULL

if head1->data <= head2->data

swap = head1

head1 move to next

else

swap = head2

head2 move to next

temphead->next = swap

temphead = swap

end while loop

if head1 is not NULL tempHead->next is head1

else if head 2 is not NULL tempHead->next is head2

return newHead

int len = 0

new node temp = head

start while loop -> temp != NULL

len++

temp move to next

end while loop

if n > len return head

else if n == len return head->next

else

difference is len - n

new node previous as NULL

new node current as head

for i < diff

prev = curr

move curr to next

end for loop

prev next = curr next

return head

end else

<functioning part>

if curr node == NULL, return

if n == 1

new insert node

insert node->next = current node's next

curr's next = insertnode

return

if curr's next == NULL AND n >= 1

insert node->next = NULL

curr's next = insertnode

return

return recursion with current node, n - 1, inserting value

<main part>

if list's head == NULL

return as new head

return functioning part with head of the list, n, inserting value

ListAddStar iterative sol:

newnode = newnode

base case: if size of list == 0 :

set head and tail of list to newnode.

else {

make the newnode point to the head

make the heads previous point to newnode

make the head newnode finally

update size.

ListAddEnd - iterative pseudo:

base case: if the size of the list == 0

set head and tail to newnode

else {

make the newnodes prev the tail

make the tails next the newnode

finally make tail newnode

update size.

newNode iterative sol:

malloc newnode

if newnode null print error

make newnode value the value

newnode nex and prev is null, return the newnode.

ListDeleteEnd solution:

this function deletes an element from the end of the list and returns its value

make a pointer *nodetodelete equal to the tail

make the list's tail the prev of the tail

if there was a second last node (check if nodetodelete's prev is not null),
then make nodetodelete->prev->next equal to NULL

otherwise, our list only has one node so

else {

list head is NULL

store the value to return

free the node to delete

update size -

return deleted value

A doubly linked list is a type of linked list in which each node consists of 3 components:

• *prev - address of the previous node
• data - data item
• *next - address of next node

current node 1 = LL1's head

current node 2 = LL2's head

bool same = true

start while loop where curr1 is not NULL && curr2 is not NULL

if same is false, return false

if current 1's data and current 2's data are not equal, same = false

move curr1 and curr2 pointer to next

exit while loop

if curr1 is NULL but curr2 is not, different sized linked list so return false

else if curr2 is NULL but curr1 is not, also different sized linked list so return false

return true (where LL1 and LL2 has exactly same value & length)

struct node previous with NULL

struct node current with given parameter node (head, curr, root....etc)

struct node next with NULL

start while loop

next is current's next

current next will now point the previous (to reverse the linked list)

and move prev->curr & curr->next to move the pointer of linked list

head = prev

return the head of linked list

Bubble sort

linear search

binary search

binary search recursion

Linear&binary search complexity

/ Define the structure for a queue node struct Node {
    int data;
    struct Node* next;
};
// Define the structure for the queue struct Queue {
    struct Node* front;
    struct Node* rear;
};
// Function to create a new queue node 
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// Function to initialize a new queue 
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    if (queue == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    queue->front = queue->rear = NULL;
    return queue;
}
// Function to enqueue a node into the queue 
void enqueue(struct Queue* queue, int data) {
    struct Node* newNode = createNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}
// Function to dequeue a node from the queue 
int dequeue(struct Queue* queue) {
    if (queue->front == NULL) {
        fprintf(stderr, "Queue is empty\n");
        exit(EXIT_FAILURE);
    }
    struct Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}
// Function to destroy the queue and free memory 
void destroyQueue(struct Queue* queue) {
    while (queue->front != NULL) {
        struct Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
    }
    free(queue);
}

int main() {
    struct Queue* queue = createQueue(); // Initialize a new queue
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    printf("Dequeued element: %d\n", dequeue(queue)); // Dequeue and print 10
    printf("Dequeued element: %d\n", dequeue(queue)); // Dequeue and print 20
    enqueue(queue, 40);
    printf("Dequeued element: %d\n", dequeue(queue)); // Dequeue and print 30
    destroyQueue(queue); // Free memory
    return 0;
}

// Define the structure for a stack node struct Node {
    int data;
    struct Node* next;
};
// Function to create a new stack node 
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
// Function to push a node onto the stack 
void push(struct Node** stack, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *stack;
    *stack = newNode;
}
// Function to pop a node from the stack 
int pop(struct Node** stack) {
    if (*stack == NULL) {
        fprintf(stderr, "Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    struct Node* temp = *stack;
    int data = temp->data;
    *stack = (*stack)->next;
    free(temp);
    return data;
}
// Function to destroy the stack and free memory 
void destroyStack(struct Node** stack) {
    while (*stack != NULL) {
        struct Node* temp = *stack;
        *stack = (*stack)->next;
        free(temp);
    }
}

int main() {
    struct Node* stack = NULL; // Initialize an empty stack
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printf("Popped element: %d\n", pop(&stack)); // Pop and print 30
    printf("Popped element: %d\n", pop(&stack)); // Pop and print 20
    push(&stack, 40);
    printf("Popped element: %d\n", pop(&stack)); // Pop and print 40
    destroyStack(&stack); // Free memory
    return 0;
}

bool FbUnfriend(Fb fb, char *name1, char *name2) {

int id1 = nameToId(fb, name1);

int id2 = nameToId(fb, name2);

assert(id1 != id2);

if (fb->friends[id1][id2]) {

fb->friends[id1][id2] = false;

fb->friends[id2][id1] = false;

return true;

} else {

return false;

}

}

List FbMutualFriends(Fb fb, char *name1, char *name2) {

int id1 = nameToId(fb, name1);

int id2 = nameToId(fb, name2);

List l = ListNew();

for (int id = 0; id < fb->numPeople; id++) {

if (fb->friends[id1][id] && fb->friends[id2][id]) {

ListAppend(l, fb->names[id]);

}

}

return l;

}

void FbFriendRecs1(Fb fb, char *name) {

int id1 = nameToId(fb, name);

// Collect mutual friend counts

int *counts = calloc(fb->numPeople, sizeof(int));

assert(counts != NULL); // lazy error checking

for (int id2 = 0; id2 < fb->numPeople; id2++) {

if (fb->friends[id1][id2]) {

for (int id3 = 0; id3 < fb->numPeople; id3++) {

if (fb->friends[id2][id3] && !fb->friends[id1][id3] && id1 != id3) {

counts[id3]++;

}

}

}

}

// Print friend recommendations

printf("%s's friend recommendations\n", name);

for (int i = fb->numPeople - 2; i > 0; i--) {

for (int id = 0; id < fb->numPeople; id++) {

if (counts[id] == i) {

printf("\t%-20s%4d mutual friends\n", fb->names[id], i);

}

}

}

free(counts);

}

/*

===============

FbUnfriend

===============

- Worst case time complexity: O(log n)

===============

FbMutualFriends

===============

- Worst case time complexity: O(n)

===============

FbFriendRecs1

===============

- Worst case time complexity: O(n^2)*/

#include <assert.h>

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include "Graph.h"

int maxDegreeDiff(Graph g) {

// TODO

int *diff = calloc(g->nV, sizeof(int));

for (int i = 0; i < g->nV; i++) {

for (AdjList curr = g->edges[i]; curr != NULL; curr = curr->next) {

diff[i]++;

diff[curr->v]--;

}

}

int maxDiff = 0;

for (int i = 0; i < g->nV; i++) {

if (abs(diff[i]) > maxDiff) {

maxDiff = abs(diff[i]);

}

}

free(diff);

return maxDiff;

}

#include <assert.h>

#include <stdbool.h>

#include <stdio.h>

#include <stdlib.h>

#include "list.h"

List flas(List l) {

List flas = NULL;

int flasLen = 0;

List curr = l;

while (curr != NULL) {

List start = curr;

int len = 1;

while (curr->next != NULL && curr->next->value > curr->value) {

len++;

curr = curr->next;

}

if (len > flasLen && len >= 2) {

flas = start;

flasLen = len;

}

curr = curr->next;

}

return flas;

}

/*

* SinglyLinkedListNode {

* int data;

* SinglyLinkedListNode* next;

* };

*

*/

bool compare_lists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {

SinglyLinkedListNode *curr1 = head1;

SinglyLinkedListNode *curr2 = head2;

bool same = true;

while (curr1 != NULL && curr2 != NULL) {

if (same == false) {

return false;

}

if (curr1->data != curr2->data) {

same = false;

}

curr1 = curr1->next;

curr2 = curr2->next;

}

if (curr1 == NULL && curr2 != NULL) {

return false;

} else if (curr1 != NULL && curr2 == NULL) {

return false;

}

return true;

}

/* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* reverseList(struct ListNode* head){

struct ListNode* prev = NULL;

struct ListNode* current = head;

struct ListNode* next = NULL;

while (current != NULL) {

next = current->next;

current->next = prev;

prev = current;

current = next;

}

head = prev;

return head;

}

STACK:

• list of items, where items can only be added/removed in first-in-last-out (FILO) order -- add to top, take from top
• e.g. cafeteria trays or wikipedia rabbit-holes (build up in one direction + only backtrack in reverse order)
• potential functions: create , push (add to top), pop (remove from top), destroy
• can be implemented using arrays, linked lists, doubly linked lists, etc.

QUEUE:

• list of items, where items can only be added/removed in first-in-first-out (FIFO) order -- add to end, take from start
• e.g. taking turns in a game (always go back and join the end of the line)
• potential functions: create , enqueue (add to end), dequeue (remove from start), destroy

(12)

• allows design by contract
• allows future developers to remove/upgrade data structure or function (e.g. for greater efficiency of same functionality), without affecting any code that uses the data structure
• keeps data structure valid (so long as ADT is well-tested, it can’t be directly changed from outside the .c file) → user can only manipulate data structure using defined functions
• restricts unauthorised access/manipulation

(12)

Hash tables do not maintain the order of items, which would make it difficult to implement Pop and PrintInOrder efficiently.

Ordered linked lists and ordered arrays incur an O(n) cost for Push due to needing to find the correct position to insert (in the case of linked lists) or to shift items (in the case of arrays).

For an AVL tree that is ordered by priority:

- Push is O(log n), as we simply insert into the AVL tree

- Pop is O(log n), as we simply delete the highest priority item from the

AVL tree

- PrintInOrder is O(n), as we simply perform a reverse in-order traversal

For a heap:

- Push is O(log n)

- Pop is O(log n)

- However, a heap does not store a global ordering of items, only a heap ordering where each item is greater than its children. To implement PrintInOrder we must pop all the items and print each item as it is removed. This is O(n log n). We then need to re-insert all the items, as PrintInOrder is not supposed to modify the heap, which is O(n log n).

Reference: Sample Exam answers

These linked lists are composed of two structs, a wrapper/container struct called "listRep" and a struct called "node". (The struct names I'm using are similar or the same as the ones used in labs and lectures.)

This "next" and "prev" pointers allow us to traverse the list forwards AND backwards. (Hence the name doubly linked list). Here is a diagram based on a diagram by Sim to better understand this type of linked list:

I'm not sure if people can comment under this but please let me know if I got anything wrong or if you have a better way of explaining doubly linked lists.