COMP2521 Week 1 - Array & Linked List Revision

📋 Lab Tasks Overview 📋 实验任务概览

Task任务	File文件	Description描述
Task 1	`arrayShift.c`	Shift array to the right n times数组右移 n 次
Task 2	`listShift.c`	Shift linked list to the right n times链表右移 n 次
Task 3	`arrayInsertOrdered.c`	Insert value into sorted array有序数组插入
Task 4	`listInsertOrdered.c`	Insert value into sorted linked list有序链表插入

🔄 Task 1: Array Shift 🔄 任务 1：数组右移

What is Array Right Shift? 什么是数组右移？

Right shift means moving the last element to the front, and all other elements move one position to the right. 右移意味着把最后一个元素移到最前面，其他所有元素向右移动一位。

Example: Right Shift 1 Time 例子：右移 1 次

Original:  [16, 5, 2, -3, 4]
After 1:   [4, 16, 5, 2, -3]
            ↑
            Last element (4) moves to front

Example: Right Shift 3 Times 例子：右移 3 次

Original:  [16, 5, 2, -3, 4]
After 1:   [4, 16, 5, 2, -3]
After 2:   [-3, 4, 16, 5, 2]
After 3:   [2, -3, 4, 16, 5]

Algorithm 算法步骤

Steps for Each Shift: 每次右移的步骤：

Save the last element: last = arr[size - 1]保存最后一个元素：last = arr[size - 1]
Move all elements right (from end to start)所有元素向右移动（从后往前）
Put last element at front: arr[0] = last把最后一个元素放到最前面：arr[0] = last

Code Implementation 代码实现

void shift(int *arr, int size, int n) {
    // Handle edge cases
    if (size <= 0 || n <= 0) {
        return;
    }

    // Optimization: shifting size times = no change
    n = n % size;

    // Repeat n times
    for (int i = 0; i < n; i++) {
        // 1. Save last element
        int last = arr[size - 1];

        // 2. Move all elements right (from end to start)
        for (int j = size - 1; j > 0; j--) {
            arr[j] = arr[j - 1];
        }

        // 3. Put last at front
        arr[0] = last;
    }
}

🔗 Task 2: Linked List Shift 🔗 任务 2：链表右移

Concept 概念

Same as array shift, but for linked lists. Move the last node to the front. 和数组右移一样，但是针对链表。把最后一个节点移到最前面。

Original:  16 -> 5 -> 2 -> -3 -> 4 -> NULL
After 1:   4 -> 16 -> 5 -> 2 -> -3 -> NULL
           ↑
           Last node (4) moves to front

⚠️ Constraints ⚠️ 限制条件

Cannot use malloc or free不能使用 malloc 或 free
Cannot modify integer values in nodes不能修改节点中的整数值
Only change pointers!只能改变指针！

Algorithm 算法步骤

Steps for Each Shift: 每次右移的步骤：

Find the last node (last) and its previous node (prev)找到最后一个节点（last）和它的前一个节点（prev）
Disconnect last: prev->next = NULL断开最后一个节点：prev->next = NULL
Put last at front: last->next = list把最后一个放到最前面：last->next = list
Update head: list = last更新头指针：list = last

Code Implementation 代码实现

struct node *shift(struct node *list, int n) {
    // Edge cases
    if (list == NULL || list->next == NULL || n <= 0) {
        return list;
    }

    // Repeat n times
    for (int i = 0; i < n; i++) {
        // Find last and prev
        struct node *prev = list;
        struct node *last = list->next;

        while (last->next != NULL) {
            prev = last;
            last = last->next;
        }

        // Move last to front
        prev->next = NULL;      // prev becomes last
        last->next = list;      // last points to old head
        list = last;            // last becomes new head
    }

    return list;
}

📥 Task 3: Array Insert Ordered 📥 任务 3：有序数组插入

Problem 问题

Given a sorted array, insert a new value while keeping the array sorted. 给定一个已排序的数组，插入一个新值并保持数组有序。

Array: [2, 5, 7, 8, _, _]  (size = 4, has extra space)
Insert: 6

Result: [2, 5, 6, 7, 8, _]

Algorithm 算法步骤

Find insertion position (from end)找到插入位置（从后往前）
Shift elements right to make space向右移动元素腾出空间
Insert the new value插入新值

Code Implementation (Method 1: From End) 代码实现（方法 1：从后往前）

void insertOrdered(int *arr, int size, int value) {
    // Find position from end
    int i = size;
    while (i > 0 && arr[i - 1] > value) {
        arr[i] = arr[i - 1];  // Shift right
        i--;
    }

    // Insert value
    arr[i] = value;
}

Code Implementation (Method 2: Find Position First) 代码实现（方法 2：先找位置）

void insertOrdered(int *arr, int size, int value) {
    // Find insertion position
    int pos = 0;
    while (pos < size && arr[pos] < value) {
        pos++;
    }

    // Shift elements right (from end)
    for (int i = size; i > pos; i--) {
        arr[i] = arr[i - 1];
    }

    // Insert value
    arr[pos] = value;
}

📥 Task 4: Linked List Insert Ordered 📥 任务 4：有序链表插入

Three Cases 三种情况

Case 1: Insert at Front

List: 5 -> 7 -> 8 -> NULL
Insert: 2

Result: 2 -> 5 -> 7 -> 8 -> NULL

Case 2: Insert in Middle

List: 2 -> 5 -> 8 -> NULL
Insert: 6

Result: 2 -> 5 -> 6 -> 8 -> NULL

Case 3: Insert at End

List: 2 -> 5 -> 7 -> NULL
Insert: 9

Result: 2 -> 5 -> 7 -> 9 -> NULL

Code Implementation 代码实现

struct node *insertOrdered(struct node *list, int value) {
    // Create new node
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->next = NULL;

    // Case 1: Empty list or insert at front
    if (list == NULL || value < list->value) {
        newNode->next = list;
        return newNode;
    }

    // Find insertion position
    struct node *curr = list;
    while (curr->next != NULL && curr->next->value < value) {
        curr = curr->next;
    }

    // Insert after curr
    newNode->next = curr->next;
    curr->next = newNode;

    return list;
}

📊 Summary: Array vs Linked List 📊 总结：数组 vs 链表

Operation操作	Array数组	Linked List链表
Shift right右移	Move elements with loop用循环移动元素	Change pointers改变指针
Insert ordered有序插入	Find position, shift elements找位置，移动元素	Find position, change pointers找位置，改变指针
Memory内存	Contiguous连续	Dynamic (malloc)动态（malloc）
Time complexity时间复杂度	O(n)	O(n)