List

Definition

A finite, ordered sequence of data items known as elements

• By ordered, we mean that there is a 1st element, 2nd element, so on
• There is no requirement of uniqueness, unlike a Set

Main operations

• create : new list of certain capacity
• add, delete
• traverse (and similar)

Implementation

• Linked list

Python implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def insert(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
 
    def locate(self, x):
        current = self.head
        while current != None:
            if current.data == x:
                return True
            current = current.next
        return False
 
    def retrieve(self, position):
        current = self.head
        count = 0 
        while (current):
            if (count == position):
                return current.data
            count += 1
            current = current.next
 
    def delete(self, key):
         
        temp = self.head
 
        
        if (temp is not None):
            if (temp.data == key):
                self.head = temp.next
                temp = None
                return
 
        
        while(temp is not None):
            if temp.data == key:
                break
            prev = temp
            temp = temp.next
 
        
        if(temp == None):
            return
 
        
        prev.next = temp.next
 
        temp = None
        
my_list=LinkedList()
my_list.insert(3)
my_list.insert(2)
my_list.insert(1)
 
print(my_list.locate(1))
print(my_list.retrieve(1))

• Array (arraylist), often a Dynamic array that changes size as needed

C dynamic array implementation

#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
    void **array;
    int size;
    int capacity;
} List;
 
void init(List *list) {
    list->size = 0;
    list->capacity = 1;
    list->array = malloc(list->capacity * sizeof(void *));
}
 
void insert(List *list, void *data) {
    if (list->size == list->capacity) {
        list->capacity *= 2;
        list->array = realloc(list->array, list->capacity * sizeof(void *));
    }
    list->array[list->size++] = data;
}
 
void delete(List *list, int index) {
    if (index < 0 || index >= list->size) {
        printf("Invalid index\n");
        return;
    }
    for (int i = index; i < list->size - 1; i++) {
        list->array[i] = list->array[i + 1];
    }
    list->size--;
}
 
void* get(List *list, int index) {
    if (index < 0 || index >= list->size) {
        printf("Invalid index\n");
        return NULL;
    }
    return list->array[index];
}
 
void print(List *list) {
    for (int i = 0; i < list->size; i++) {
        printf("%d ", *(int *)list->array[i]);
    }
    printf("\n");
}
 
int main() {
    List list;
    init(&list);
 
    int x = 1;
    int y = 2;
    int z = 3;
 
    insert(&list, &x);
    insert(&list, &y);
    insert(&list, &z);
 
    for (int i = 0; i < list.size; i++) {
        printf("%d ", *(int *)get(&list, i));
    }
    printf("\n");
 
    delete(&list, 1);
 
    for (int i = 0; i < list.size; i++) {
        printf("%d ", *(int *)get(&list, i));
    }
    printf("\n");
 
    return 0;
}

---

• task Add time complexity details
• task Add adv/disadv