Implementation and Analysis of Lists

 

2025-Data-Structures/03-List at main · sihyes/2025-Data-Structures

자료. Contribute to sihyes/2025-Data-Structures development by creating an account on GitHub.

github.com

Assignment Goals

  1. Implementation of insertting a new node in the beginning or at the end of doubly linked list using `dinsert_node`
  2. Implementation of a merge function using a linked list that generates a new linked list c by merging a and b
  3. analyze the time complexity.
  4. Implementation of the `List ADT`(p55-p61) as well as add_first, add_last, delete_first, delete_last. 
  5. (includes executing example code.)

#1. Introduction(Theoretical Background, Logic)

 
Please refer to the Appendix (link) for detailed explanations. The content is long, so it’s attached as a reference.
 
A `list` is a collection of elements of the same data type. Among them, there are tow main types: arrays and linked lists.
An `array` has a fixed size. When inserting or deleting elements, it can cause overhead in memory and performance.
A `linked list`, on the other hand, allows easy insertion and deletion and has no size limitation, but it is harder to implement. A linked list is made up of a collection of nodes.
Each node has two parts: a data field and a link field (a pointer to the next node).
There are three main types of linked lists:

  1. Singly Linked List – Each node connects in one direction, from one node to the next.
  2. Circular Linked List – The last node links back to the first node, forming a circle.
  3. Doubly Linked List – Each node has two links, one pointing to the previous node and one to the next node.
    This makes it easier to traverse in both directions but consumes more memory.

In linked lists, the head pointer (or head node) plays an essential role as it indicates where the list starts.
Sometimes, programmers use a “pointer to a pointer” (double pointer) when managing or modifying the list structure.

Feature Array Linked List
Memory Allocation Fixed size (static) Dynamic (grows as needed)
Insertion/Deletion Slow (requires shifting elements) Fast (adjusts links)
Access Time Fast (direct indexing) Slow (must traverse nodes)
Implementation Easy More complex
Memory Use Efficient Requires extra memory for links
Size Limit Fixed No limit (until memory runs out)

 

Type Structure Pros Cons
Singly Linked List One link per node (next) Simple and easy to implement One-way traversal only
Circular Linked List Last node links to first Can traverse continuously Harder to manage end conditions
Doubly Linked List Two links per node (prev, next) Bidirectional traversal Higher memory usage

#2. Problem Definition

In this assignment, three different implementations are required:

  1. When inserting a new node in the beginning or at the end of in doubly linked list, explain whether or not ‘dinsert_node’ can be used in p41 of ‘DS-Lec04-List.pdf’. If so, explain the reason. Otherwise, implement ‘dinsert_first_node’ and ‘dinsert_last_node’.
  2. Suppose two linked lists `a = {a1,a2, ... ,am}` and `b = {b1,b2, ... ,bm}`  are sorted in an ascending order. Implement a merge function using a linked list that generates a new linked list c by merging a and b. Here, elements should be sorted in an ascending order. Show the result using the following example. Also, analyze the time complexity (upper bound Ο or tight bound θ) of this function.
    a = {1,2,5,10,15,20,25} , b = {3,7,8,15,18,30} → c = {1,2,3,5,7,6,10,15,15,18,20,25,30}
  3.  When a linked list is defined as below, re-implement all functions in ‘List ADT’ (p55-p61) as well as add_first, add_last, delete_first, delete_last. Then, run the following example code.

#3. Algorithm and Data Structure

In this project, the main data structure used was the linked list, including singly, circular, and doubly linked lists.
Unlike arrays, linked lists allow dynamic memory allocation, which makes insertion and deletion more efficient without shifting elements.
For the doubly linked list, each node contains data and two pointers (llink, rlink), enabling bidirectional traversal.
The insertion algorithm (dinsert_node) was analyzed, and additional functions for inserting at the beginning and end were considered for clarity and flexibility.
A merge algorithm was also implemented to combine two sorted linked lists into a single sorted list.
This algorithm compares nodes from both lists one by one, attaching the smaller value each time, with a time complexity of Θ(n + m). 
Overall, these data structures and algorithms demonstrate how dynamic lists can efficiently manage ordered data and support operations such as insertion, deletion, and merging.
 

#4. Implementation Results and Analysis

4.1 Can `dinsert_node()` perform insertion at the beginning and at the end?

About the first question, implementation about the p41 is over below. 

void dinsert_node(DlistNode *before, DlistNode *new_node) {
    new_node -> llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink = new_node;
}

The function `dinsert_node()` can also be used to insert a new node at the beginning or at the end of a doubly linked list. 
Because the list has a head node, the insertion operation can be performed in the same way as for other nodes by adjusting the links of the head node. 
Therefore, it is not necessary to implement separate functions such as 
`dinsert_first_node()` or `dinsert_last_node()`.

void dinsert_first_node(DlistNode *head, DlistNode *new_node) {
    dinsert_node(head, new_node);
}
void dinsert_last_node(DlistNode *head, DlistNode *new_node) {
    dinsert_node(head->llink, new_node);
}
int main() {
    DlistNode head_node;
    DlistNode *p[8];

    init(&head_node);
    for (int i=0; i<5; i++) {
        p[i] = (DlistNode *)malloc(sizeof(DlistNode));
        p[i] -> data = i;
        if (i==0){dinsert_node(&head_node, p[i]);}
        else dinsert_node(p[i-1],p[i]);
    }
    display(&head_node);

    p[5] = (DlistNode *)malloc(sizeof(DlistNode));
    p[5] -> data = 5;
    dinsert_last_node(&head_node,p[5]); // headnode의 llink가 마지막노드! 마지막노드에 삽입해줘용
    display(&head_node);

    p[6] = (DlistNode *)malloc(sizeof(DlistNode));
    p[6] -> data = 6;
    dinsert_first_node(&head_node,p[6]); //제일 앞에 넣어줍니다.
return 0;
}

because doubly linked list has 'head node', we do not need to implement any `dinsert_first_node` function.

This image shows that `dinsert_node()` can perform the insertion without`dinsert_first_node()`.
 
In doubly linked list, the head node connects both ends of the list. `head->rlink` points to the first node, and `head->llink` points to the last node (the tail). To insert a new node at the beginning, we can use `dinsert_node(head, new_node)`.
To insert at the end, we use `dinsert_node(head->llink, new_node)`, which adds the node after the last one.
Therefore, `dinsert_node()` alone can handle both front and rear insertions without extra functions.

4.2 Merge two linked lists.

4.2.1 implementation

First, we need to make the two base linked lists.
So, I made a `createList()` function that turns an array into a linked list and returns the head's address.

ListNode *createList(int arr[], int size) {
    if (size == 0) return NULL;
    ListNode *head = (ListNode *) malloc(sizeof(ListNode));
    head->data = arr[0];
    head->link = NULL;

    ListNode *current = head;
    for (int i = 1; i < size; i++) {
        ListNode *new_node = (ListNode *) malloc(sizeof(ListNode));
        new_node->data = arr[i];
        new_node->link = NULL;
        current->link = new_node;
        current = new_node;
    }
    return head;
}

In `main()`, I created two arrays `a1` and `b1` and converted them into linked lists using `createList()`.
Then, I called `merge(a, b)` and displayed the result:

int main() {
    int a1[] = {1, 2, 5, 10, 15, 20, 25};
    int b1[] = {3, 7, 8, 15, 18, 30};
    ListNode *a = createList(a1, 7);
    ListNode *b = createList(b1, 6);

    ListNode * c = merge(a,b);
    display(c);
    return 0;
}

The logic of `merge()` is simple:
It iterates until either `head1` or `head2` reaches the end (`link == NULL`).
During the iteration, the smaller value between the two heads is added to a dummy node.
After one of the lists is finished, the remaining items from the other list are added.
Finally, the merged linked list starting from `dummy.link` is returned.

ListNode *merge(ListNode *head1, ListNode *head2) {
    ListNode dummy;
    ListNode *p = &dummy;
    dummy.link = NULL;

    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    else {
        while (head1 != NULL && head2 != NULL) {
            if (head1->data <= head2->data) {
                p->link = head1;
                head1 = head1->link;
            } else {
                p->link = head2;
                head2 = head2->link;
            }
            p = p->link;
        }

        if (head1 != NULL) p->link = head1;
        if (head2 != NULL) p->link = head2;
        return dummy.link;
    }
}

code running result

4.2.2 Time Complexity

The merge function goes through each element of the two linked lists one by one.
Each comparison and linking operation happens exactly once per element.
After one list is finished, the remaining elements of the other list are added directly.
Since every element is processed only once, the total number of operations is proportional to the total number of elements, which is `n = m + n`.
Therefore, the time complexity of this merge function is Θ(n).

4.3 List ADT

I implemented a singly linked list using a `ListType` structure that keeps track of the head, tail, and length of the list.
All functions from the List ADT were re-implemented, including `add()`, `delete_()`, `get_entry()`, and `is_in_list()`.
Additionally, I implemented `add_first()`, `add_last()`, `delete_first()`, and `delete_last()` to handle insertions and deletions at both ends of the list efficiently.
Each operation updates the head, tail, and length properly to maintain the list structure.
Memory allocation for new nodes is handled using `malloc()`, and removed nodes are freed with `free()` to prevent memory leaks.

void add_first(ListType *list, element data) {
    ListNode *new_node = (ListNode *) malloc(sizeof(ListNode));
    new_node->data = data;
    if (list->head == NULL) {
        list->head = list->tail = new_node;
        new_node->link = NULL;
    } else {
        new_node->link = list->head;
        list->head = new_node;
    }
    list->length++;
}

void add_last(ListType *list, element data) {
    ListNode *new_node = (ListNode *) malloc(sizeof(ListNode));
    new_node->data = data;
    if (list->tail == NULL) {
        list->head = list->tail = new_node; //tail== null->>> head ==null
    } else {
        list->tail->link = new_node;
        list->tail = new_node;
    }
    new_node->link = NULL;
    list->length++;
}

void delete_first(ListType *list) {
    ListNode *p = list->head;
    list->head = list->head->link;
    free(p);
    if (list->head == NULL) list->tail = NULL; //list비면 tail도 비워줘야함
    list->length--;
}

When a deletion made the list empty, both the head and tail pointers were set to NULL to correctly represent an empty list.
The list maintained the correct order and structure after all operations, and functions like is_in_list() and get_entry() returned expected results.

running results

 

 

#5. My Learning Points

By actually implementing doubly linked lists and singly linked lists, the confusion in my mind has finally been cleared up.
Although I understood the concepts during lectures, when I tried to implement them myself, not every line worked as expected, and only parts of it existed clearly in my mind. This made me go back and review the lecture materials.
Through this process, I learned a lot about how pointers display addresses in memory and the details of memory management.
I also realized that in C++, `delete` is a reserved keyword, which requires careful attention.
Overall, implementing the lists by myself helped me understand the concepts much more deeply than just listening to the lectures.

Appendix

'컴퓨터공학과 > Data structures' 카테고리의 다른 글

[자료구조] Priority, Heap  (0) 2025.11.05
Assignment05 Technical Report  (0) 2025.10.27
Assignment04_Technical report  (0) 2025.10.10
[자료구조] List  (0) 2025.10.08
Assignment02 _ Technical Report  (0) 2025.09.24

티스토리툴바