Singly Linked List

The  linked list ADT consists of nodes that are linked together by a pointer.  We can think of a node programmatically as a C Structure, Node, which contains 2 variables:

  1. A variable called value , which is used to store the data in the list. Value can be set to any data type depending on what is needed
  2. A variable called next, which is a pointer to a node.

Our linked list class contains one global variable of type node pointer, which points to the first item in the list.

The list can be thought of a queue of people in a line with name tags (data), however, in this queue, people can join at the front, back and cut in line.

Operations performed on a linked list are shown below:

Add(value) or AddLast(value)Adds the value to the end of the list.Someone joins the end of the line
AddFirst(value)Adds a value to the top/front of the listSomeone joins the line from the front.
Insert(value, i)Adds/inserts a value at location I counting from top/frontSomeone cuts in line at the become the ith position in the list.  If I exceeds the size of the list, the person is added to the end of the list
Size()Returns the size of the listFind out the amount of people on the line
IsEmpty()Returns true if the queue is empty, i.e, size==0Find out if the line is empty.
Delete(i)Deletes a node at location iSomeone leaves the line from the ith location
Some operations that are performed on a linked list.

Some Linked List algorithms

Performing the operations above is not as straightforward as our previous ADTs.  In this discussion, we examine the algorithms for performing operations in the list.



Add First

	Create the new Node newListItem
	newListItem.value <-- newValue  <--first

Add last

Create the new Node newListItem
newListItem.value  newValue

If the list is empty Then
       first <-- newListItem <-- NULL
	Create Nodes currentNode, previousNode

In class assignment/homework 1

The rest of the operations  on the linked list were omitted:

3Insert(value, i)

Using to the algorithms above as a guide, write separate algorithms which implements the operation listed in the table above.

Code for a linked list in C

//Note that the operations from the in class assignment/homework are not included.
#include <stdio.h>
#include <stdlib.h>

/*keep track of the size of the list.
Initially, the size is 0,
thus  the count is 0.*/
int count = 0;

/*create a structure called "Node_n"
and give it a type definition
named Node.
We do this to avoid using the
"struct" keyword everytime
we declare a  Node_n structure.

It's simply a quality of life improvement
typedef struct Node_n
    int data;
    struct Node_n * next;/*note that we cant
                        use the typedef here ,
                        e.g "struct Node * next;"
                        since the type definition
                        has not been created yet.
                        if used it will produce
                        a warning when you try to
                        assign Node Structures to
                        each other such as in the
                        add function etc:
                        "assignment from incompatible
                        pointer type
} Node;

/*we declare Node structure to
represent the first item at the
start of the list.

It is assigned a mull pointer value,
which can be thought of a value of
0 for the pointer.
Node * first;

void addFirst(int value);
void addLast(int value);
void insert(int value, int location);//left as student discussion  on how this should be implemented
int size();
void deleteNode(int location);
void printList();

int main()


    return 0;

void addFirst(int value)
    //create new node....
    /*we use malloc
        to allocate a portion  of
        RAM memory to store the
        data contained within a node.
        The amount of memory allocated is
        the size of the node datatype.

        the newly allocated node
        Node structure's pointer is now assigned
        to  our pointer named "newNode"

        note that "sizeof" is a unary operator
        much like the address operator "&"

        sizeof only requires parentheses
        only when  it is evaulating a data type
        so :

        int x;
        printf("%d", sizeof x);

        would complile and work fine.

    Node * newNode = malloc(sizeof (Node));
    /*Question: how different would it be create
    new node without a pointer and achieve the
    same result in the line above?*/

    // the data in the new node

    /*It is best practice to check to see of the list
    is empty and not based on the integer size being
    zero. This is because most list traversal happens
    through pointers  and must be stopped when null
    is reached. If using size to check if it's empty,
    the programmer may forget to set the last link
    in the list to be null resulting in infinite
    traversal looping*/
    //if the list is empty..
    if( first==NULL)

        first->next=NULL;/*set next to null,
                        indicating that
                        this is the last item
                        in the list so far*/

    else// the list contains items///
        //create links..
        //recall that the list is null terminated still.

/*Future exercise 3:
adde a node called last which always
stores the last item in the list.
modify addFirst to ensure that
add first is being tracked.
modify this code to omit the
traversal using the while loop*/

void addLast(int value)
    /*What would happen if we used node
    structures instead of pointers?
    try to implement this function without
    delaring pointers,
    i.e declare newNode,currentNode,
    previousNode as a node and not a pointer
    to a Node
    Answer: when current is set to null, we will
    not be able to dereference the null value to
    a node so that current can now bw assigned
    to a NULL node. There is no such thing
    as a null struct, only null pointers*/
    Node * newNode = malloc(sizeof(Node));;

    newNode->data = value;
    newNode->next = NULL;

    //if the list is empty
        Node * currentNode , * previousNode;


        /*while  the end of the list
        has not been reached*/
        /*loop terminates with previousNode
        being the last one in the list

void printList()
    printf("Start list...\n");
    Node * current = first;
    while (current !=NULL)
        printf("%d\n", current->data);
        current=(Node *)(current->next);
    printf("End list...\n");

int size()
    return count;

In class assignment/homework 2

The rest of the operations on the linked list  were omitted in the code:

2Insert(value, i)

Using to the Code  above as a guide, write functions which implements the operation listed in the table above. Update your main method to test the operations so that they behave as expected.

© 2020  Vedesh Kungebeharry. All rights reserved. 

One thought on “Singly Linked List

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s