Module 0 (Linked List)

Linked List

Terminology

Before going into the definition, there are some terms that are frequently used in describing a linked list.

Node – A node represents one data element that can contain a value and/or other information needed, as well as its relations/reference to another node.
Head – is the first node of a linked list.
Tail – is the last node of a linked list.

Definition

Linked List is a data structure that can store data linearly, in which these data are represented by a collection of nodes that are sequential. Fundamentally, a node in a linked list consists of:

Data to be stored
Reference (link) to the next node

Illustration of a node in a linked list.

first image

Characteristics

Linked list is a dynamic data structure, meaning that the size of one can change accordingly to the number of data that are being added, unlike Static Array. However, the data in a linked list cannot be accessed randomly like accessing an index of an array. To access the data, the linked list needs to go through a traversing process first.

Illustration

Linked list can be illustrated as a collection of nodes that are linked to each other sequentially, creating a chain of sequence. For example, a list 𝐴 with a set of data such as 𝐴 = [2,3,6,11,13].

first illustration

Basic Operation

isEmpty - to check whether a list is empty or not.
pushBack - to insert new data from the back of the list.
pushFront - to insert new data from the front of the list.
insertAt - to insert new data at the desired position.
back - to retrieve data from the back of the list.
front - to retrieve data from the front of the list.
getAt - to retrieve data from a certain position.
popBack - to remove data from the back of the list.
popFront - to remove data from the front of the list.
remove(x) - to remove data x that shows up first in the list.

Linked List Variations

Singly-Linked List

Node in a Singly-Linked List can only store a reference/link to the next node. Usually this reference is represented by the variable next.
Doubly-Linked List

In a Doubly-Linked List, each node has two references/link, which are a link that points towards the next node, and one towards to previous node. These two references/links usually are called as next and prev (previous)

first meme

ADT Implementation: `SinglyList`

Complete implementation of SinglyList can be accessed here

This a representation and implementation of a Singly Linked List that stores the int data type. This representation will be brought in the shape of an Abstract Data Type (ADT) that will become a new data type called SinglyList.

singly list linked list

Here is the list of time complexity in this implementation:

Operation	Function	Time complexity
pushBack	Inserting new data from the back.	O($N$)
pushFront	Inserting new data from the front.	O($1$)
insertAt	Inserting new data at a certain position.	O($N$) (Worst-case)
popBack	Removing node from the back.	O($N$)
popFront	Removing node from the front.	O($1$)
remove(x)	Removing first data with the value x.	O($N$) (Worst-case)
front	Retrieving value of the first node.	O($1$)
back	Retrieving value of the last node.	O($N$)
getAt	Retrieving value of a node at a certain position	O($N$) (Worst-case)
isEmpty	Checking whether the list is empty or not.	O($1$)

Linked List implementation on C++ Language could be done with std::list.

#include <list>

int main(){
    std::list<int> l;
    return 0;
}

Node Representation

Nodes can be represented by a struct named SListNode that stores the data variable (with an int data type), and is referenced to the next node, that is next.
```
typedef struct snode_t {
    int data;
    struct snode_t *next;
} SListNode;
```

SinglyList Structure

typedef struct slist_t {
    unsigned _size;
    SListNode *_head;
} SinglyList;

isEmpty

To check if the list is empty or not, check whether the head of the list has a NULL value or not.

bool slist_isEmpty(SinglyList *list) {
    return (list->_head == NULL);
}

Here is std::list's function to check if a list is empty or not.

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    if(l.empty()){
        std::cout << "List ini kosong" << std::endl;
    }

    return 0;
}

pushBack

Generally, the steps to do a pushBack are as follows:

Create a new node
If it's an empty list, then it's clear that the head is the new node.

If the list is not empty, search through the entire list until the end, and point the last node to the new node. This process of searching can be done with the help of a temporary variable which is temp.

void slist_pushBack(SinglyList *list, int value)
{
    SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
    if (newNode) {
        list->_size++;
        newNode->data = value;
        newNode->next = NULL;
        
        if (slist_isEmpty(list)) 
            list->_head = newNode;
        else {
            SListNode *temp = list->_head;
            while (temp->next != NULL) 
                temp = temp->next;
            temp->next = newNode;
        }
    }
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    
    while(!l.empty()){
        /*
        due to linked list structure is different compared to array structure
        iteration on linked list is different too
        */
        std::cout << l.front() << std::endl;
        l.pop_front();
    }

    return 0;
}

pushFront

To do a pushFront, the steps are as follows.

Create a new node.
If the list is empty, make the new node as head.

If the list is not empty, then it's clear that next from the new node is head.

void slist_pushFront(SinglyList *list, int value) 
{
    SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
    if (newNode) {
        list->_size++;
        newNode->data = value;
        
        if (slist_isEmpty(list)) newNode->next = NULL;
        else newNode->next = list->_head;
        list->_head = newNode;
    }
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);
    
    while(!l.empty()){
        std::cout << l.front() << std::endl;
        l.pop_front();
    }

    return 0;
}

insertAt

The insertAt operation has a pretty complicated process. There are some cases that needs to be examined.

Case 1: index is 0

Simply do a pushFront and done.

Case 2: index is at the end
Simply do a pushBack and done.

Case 3: index is at the middle
Create a new node.
With the help of temp variable, do a traversal until it reaches the position of node at index-1.
Point next from the new node towards the next node from the last node of the search result.

Connect the node from the traversal result with the new node.

void slist_insertAt(SinglyList *list, int index, int value)
{
    if (slist_isEmpty(list) || index >= list->_size) {
        slist_pushBack(list, value);
        return;    
    }
    else if (index == 0) {
        slist_pushFront(list, value);
        return;
    }
    
    SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
    if (newNode) {
        SListNode *temp = list->_head;
        int _i = 0;
        
        while (temp->next != NULL && _i < index-1) {
            temp = temp->next;
            _i++;
        }
        newNode->data = value;
        newNode->next = temp->next;
        temp->next = newNode;
        list->_size++;
    }
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    /*
    syntax below will be explained in this modul
    */

    auto pointer = l.begin();

    for(int i=0; i<2; i++){
        pointer++;
    }

    l.insert(pointer, 30);
    // 30 would be the third number on the list
    
    while(!l.empty()){
        std::cout << l.front() << std::endl;
        l.pop_front();
    }

    return 0;
}

back

Simply traverse until the end and return the value.

int slist_back(SinglyList *list)
{
    if (!slist_isEmpty(list)) {
        SListNode *temp = list->_head;
        while (temp->next != NULL) 
            temp = temp->next;
        return temp->data;
    }
    return 0;
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    std::cout << l.back() << std::endl;

    return 0;
}

front

Use the value from head.

int slist_front(SinglyList *list)
{
    if (!slist_isEmpty(list)) {
        return list->_head->data;
    }
    return 0;
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    std::cout << l.front() << std::endl;

    return 0;
}

getAt

These are some steps to do a getAt:

Do a traversal and take record of the indexes.

When the traversal reaches the desired index, return the node value.

int slist_getAt(SinglyList *list, int index)
{
    if (!slist_isEmpty(list)) {
        SListNode *temp = list->_head;
        int _i = 0;
        while (temp->next != NULL && _i < index) {
            temp = temp->next;
            _i++;
        }
        return temp->data;
    }
    return 0;
}

getAt operation on std::list could be done with iterator of std::list.

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    auto pointer = l.begin();

    for(int i=0; i<1; i++){
        pointer++;
    }

    // this program would show the second element of the list
    std::cout << *pointer << std::endl;

    return 0;
}

popBack

These are some steps to do a popBack:

Do a traversal with the help of two nodes - nextNode (next node) and currNode (current node).
If next from currNode is empty, then there is only one data. The node will be erased immediately.
Do a traversal until the end.
When it reaches the end, remove the reference from current node (currNode).

Erase the next node (nextNode)

void slist_popBack(SinglyList *list)
{
    if (!slist_isEmpty(list)) {
        SListNode *nextNode = list->_head->next;
        SListNode *currNode = list->_head;

        if (currNode->next == NULL) {
            free(currNode);
            list->_head = NULL;
            return;
        }

        while (nextNode->next != NULL) {
            currNode = nextNode;
            nextNode = nextNode->next;
        }
        currNode->next = NULL;
        free(nextNode);
        list->_size--;
    }
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    l.pop_back();

    while(!l.empty()){
        std::cout << l.front() << std::endl;
        l.pop_front();
    }

    return 0;
}

popFront

These are some steps to do a popFront:

Store head in temp (a temporary variable).
Change head with reference/next from head

Erase the temp node.

void slist_popFront(SinglyList *list)
{
    if (!slist_isEmpty(list)) {
        SListNode *temp = list->_head;
        list->_head = list->_head->next;
        free(temp);
        list->_size--;
    }
}

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    l.pop_front();

    while(!l.empty()){
        std::cout << l.front() << std::endl;
        l.pop_front();
    }

    return 0;
}

remove(x)

To do a remove(x), which is essentially erasing data x that is found first, do the steps as follows.

Case 1: Data being erased is found at the front

Simply do a popFront and then it's done.

Case 2: Data being erased is not found at the front

Do a traversal to check whether the data in the search node is the same as the one to be erased. During the search, take record of the previous node (prev) and current node (temp).
When the date is found, stop the traversal.
Connect the prev node with the next from the current node.
Remove current node (temp)

Case 3: Data is not found

When the traversal is stopped, check whether the node has a NULL value or not. If it has a NULL value, it can be determined that the data is not found.

void slist_remove(SinglyList *list, int value)
{
    if (!slist_isEmpty(list)) {
        SListNode *temp, *prev;
        temp = list->_head;

        if (temp->data == value) {
            slist_popFront(list);
            return;
        }
        while (temp != NULL && temp->data != value) {
            prev = temp;
            temp = temp->next;
        }

        if (temp == NULL) return;
        prev->next = temp->next;
        free(temp);
        list->_size--;
    }
}

On std::list, writer once again will use iterator of std::list.

#include <iostream>
#include <list>

int main(){
    std::list<int> l;

    l.push_back(5);
    l.push_back(10);
    l.push_front(1);

    auto pointer = l.begin();

    while(1){

        if(*pointer == 5){
            l.erase(pointer);
            break;
        }

        else{
            pointer++;
        }

    }

    while(!l.empty()){
        std::cout << l.front() << std::endl;
        l.pop_front();
    }

    return 0;
}

More on std::list could be read here or in C++ Language documentation here.

To Iterator >

Modul Struktur Data
Ditulis oleh tim Asisten Struktur Data 2023 - Teknik Informatika ITS

Navigasi

Home

Modul 1

Pengenalan Struktur Data IND | ENG
Dynamic Array IND | ENG
Linked List IND | ENG
Pengenalan Bahasa C++ dan Iterator Dasar IND | ENG
Soal Latihan IND | ENG
Stack IND | ENG
Queue IND | ENG
Deque IND | ENG
Priority Queue (List Based) IND | ENG
Soal Latihan IND | ENG

Modul 2

Pengenalan Tree IND | ENG
Binary Search Tree IND | ENG
Traversal BST IND | ENG
Soal Latihan IND | ENG
Self-Balancing Binary Search Tree IND | ENG
AVL Tree IND | ENG
Set dan Map IND | ENG

Modul 3

Pengenalan Graf IDN | ENG
Traversal Graf IDN | ENG
Shortest Path IND | ENG
Minimum Spanning Tree IND | ENG

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Module 0 (Linked List)

Linked List

Terminology

Definition

Characteristics

Illustration

Basic Operation

Linked List Variations

Singly-Linked List

Doubly-Linked List

ADT Implementation: `SinglyList`

Node Representation

SinglyList Structure

isEmpty

pushBack

pushFront

insertAt

back

front

getAt

popBack

popFront

remove(x)

Case 1: Data being erased is found at the front

Case 2: Data being erased is not found at the front

Case 3: Data is not found

Navigasi

Home

Modul 1

Modul 2

Modul 3

Clone this wiki locally

Module 0 (Linked List)

Linked List

Terminology

Definition

Characteristics

Illustration

Basic Operation

Linked List Variations

Singly-Linked List

Doubly-Linked List

ADT Implementation: SinglyList

Node Representation

SinglyList Structure

isEmpty

pushBack

pushFront

insertAt

back

front

getAt

popBack

popFront

remove(x)

Case 1: Data being erased is found at the front

Case 2: Data being erased is not found at the front

Case 3: Data is not found

Navigasi

Home

Modul 1

Modul 2

Modul 3

Clone this wiki locally

ADT Implementation: `SinglyList`