My linked list implementation in C

Question

I have been reading about pointers in C and I thought implementing a linked list would be a good exercise to test my knowledge.

Below is my code and it is 100% functional. All I am looking for is some criticism, such as how to make the functions more efficient or defining *pointerToLinkedList in a better spot.

#include <stdio.h>
#include <stdlib.h>

//Structure represents a node of a Linked List
struct node {
    int data;
    struct node* link;
};

//Pointer to the head node
struct node *pointerToLinkedList = NULL;

//Function inserts a new node at the beginning of the linked list
void insertNodeBeginning(int aData){
    //pointer to the new node
    struct node *newNode = (struct node*) malloc(sizeof(struct node));

    //fill in data in new node
    newNode->data = aData;
    //point new node to the previous head (now second node in linked list)
    newNode->link = pointerToLinkedList;

    //adjust pointerToLinkedList accordingly with the new head
    pointerToLinkedList = newNode;
}

//Function inserts a new node at the end of the linked list
void insertNodeEnd(int aData){

    //pointer to the new node
    struct node *newNode = (struct node*) malloc(sizeof(struct node));

    //fill in data in new node
    newNode->data = aData;
    //point new node to NULL, because its last node in list
    newNode->link = NULL;

    //link second last node to the newly created last node of the linked list
    //start at beginning of list
    struct node *secondLastNode = pointerToLinkedList;
    //loop until it becomes second last
    while(secondLastNode->link != NULL){
        secondLastNode = secondLastNode->link;
    }
    //actual linking
    secondLastNode->link = newNode;
}

//Function deletes node at the beginning of the linked list
void deleteHead(){

    //get reference of the head that will be deleted
    struct node *temp = pointerToLinkedList;

    //adjust pointerToLinkedList to the new head (previously the second node)
    pointerToLinkedList = pointerToLinkedList->link;

    //free memory of the old head       
    free(temp);
}

//Function deletes node at the end of the linked list
void deleteTail(){

    //get reference of the head to iterate through linked list
    struct node *temp = pointerToLinkedList;
    struct node *newTail;

    //iterate through linked list
    while(temp->link != NULL){
        newTail = temp;
        temp = temp->link;
    }

    //free memory of old tail
    free(newTail->link);

    //adjust the new tail and point it to NULL
    newTail->link = NULL;
}

Two more things apart from the criticism:

Am I using the free() function properly? Is the structure actually being removed from the dynamic memory?
What other functions apart from the four currently installed, would you recommend to implement as an exercise?

\$\begingroup\$ You might enjoy this video youtu.be/0ZEX_l0DFK0 \$\endgroup\$

sudo rm -rf slash
– sudo rm -rf slash

2017-10-01 16:09:32 +00:00
Commented Oct 1, 2017 at 16:09 — sudo rm -rf slash
– sudo rm -rf slash, Commented Oct 1, 2017 at 16:09

Jamal · Accepted Answer · 2017-10-08 23:12:26Z

I suggest you rename link to next which is a more conventional name for the next linked list node.
```
struct node {
    int data;
    struct node* link;
};
```
Currently, you have to write the type of the node as struct node. However, if you do:
```
typedef struct node {
    int data;
    struct node* link;
} node;
```
You can allocate a new node simply by writing node my_node;
No, no, no and no. Don't you ever use global variables. As the code base grows, if something goes wrong because of a global variable, debugging will be hell.
```
struct node *pointerToLinkedList = NULL;
```

You should not cast the result of malloc:

struct node *newNode = (struct node*) malloc(sizeof(struct node));

What comes to struct node *newNode = (struct node*) malloc(sizeof(struct node)), I suggest you write instead:
```
malloc(sizeof *newNode)
```
That way, if you change the type of *newNode to, say, some_funky_struct, you don't have to rewrite malloc(sizeof(struct node)) to malloc(sizeof(struct some_funky_struct)).
There is no pointer to the tail of your list. You define one (called, say, list_tail), you can insertNodeEnd in constant time.
I suggest you rename it to list_head, since that is a conventional name for the first node of a linked list.
```
struct node *pointerToLinkedList = NULL;
```

Normally, what you would do when implementing a singly-linked list is creating a following:

typedef struct linked_list_node_t {
    void* datum;
    struct linked_list_node_t* next;
} linked_list_node;

typedef struct linked_list_t {
    linked_list_node_t* head;
    linked_list_node_t* tail;
    size_t size;
} linked_list_t;

linked_list_t* linked_list_t_alloc() {
    linked_list_t* list = malloc(sizeof *list);

    if (!list) {
        abort();
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return list;
}

linked_list_t_operation(linked_list_t* list, ... operands) {
    ... Your implementation.
}

Alternative implementation

You could do:

singly_linked_list.h

#ifndef SINGLY_LINKED_LIST_H
#define SINGLY_LINKED_LIST_H

#include <stdlib.h>

typedef struct singly_linked_list_node_t {
    int datum;
    struct singly_linked_list_node_t* next;
} singly_linked_list_node_t;

typedef struct singly_linked_list_t {
    singly_linked_list_node_t* head;
    singly_linked_list_node_t* tail;
    size_t size;
} singly_linked_list_t;

typedef struct singly_linked_list_iterator_t {
    singly_linked_list_node_t* next_node;
} singly_linked_list_iterator_t;

/******************************************
* Allocates and returns a new empty list. *
******************************************/
singly_linked_list_t* singly_linked_list_alloc();

/**********************
* Initializes a list. *
**********************/
int singly_linked_list_init(singly_linked_list_t* list);

/*************************
* Frees the entire list. *
*************************/
void singly_linked_list_free(singly_linked_list_t* list);

/***************************
* Clears the list content. *
***************************/
void singly_linked_list_clear(singly_linked_list_t* list);

/**********************************************
* Pushes a new datum to the head of the list. *
**********************************************/
int singly_linked_list_push_front(singly_linked_list_t* list, int datum);

/**********************************************
* Pushes a new datum to the tail of the list. *
**********************************************/
int singly_linked_list_push_back(singly_linked_list_t* list, int datum);

/*****************************
* Pops the head of the list. *
*****************************/
int singly_linked_list_pop_front(singly_linked_list_t* list);

/*****************************
* Pops the tail of the list. *
*****************************/
int singly_linked_list_pop_back(singly_linked_list_t* list);

/**********************************************
* Returns the number of elements in the list. *
**********************************************/
size_t singly_linked_list_size(singly_linked_list_t* list);

/**************************************
* Returns the iterator over the list. *
**************************************/
singly_linked_list_iterator_t*
singly_linked_list_get_iterator(singly_linked_list_t* list);

/******************************************************************
* Returns non-zero value if the iterator has something to remove. *
******************************************************************/
int singly_linked_list_iterator_has_next(singly_linked_list_iterator_t* iterator);

/**************************
* Returns the next datum. *
**************************/
int singly_linked_list_iterator_next(singly_linked_list_iterator_t* iterator);

#endif /* SINGLY_LINKED_LIST_H */

singly_linked_list.c

#include "singly_linked_list.h"
#include <stdlib.h>

singly_linked_list_t* singly_linked_list_alloc()
{
    return calloc(1, sizeof(singly_linked_list_t));
}

int singly_linked_list_init(singly_linked_list_t* list)
{
    if (!list)
    {
        return 0;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    return 1;
}

void singly_linked_list_free(singly_linked_list_t* list)
{
    if (list)
    {
        singly_linked_list_clear(list);
        free(list);
    }
}

void singly_linked_list_clear(singly_linked_list_t* list)
{
    singly_linked_list_node_t* current_node;
    singly_linked_list_node_t* next_node;

    if (!list)
    {
        return;
    }

    current_node = list->head;

    while (current_node)
    {
        next_node = current_node->next;
        free(current_node);
        current_node = next_node;
    }

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

int singly_linked_list_push_front(singly_linked_list_t* list, int datum)
{
    singly_linked_list_node_t* new_node;

    if (!list)
    {
        return 0;
    }

    new_node = malloc(sizeof *new_node);

    if (!new_node)
    {
        return 0;
    }

    new_node->datum = datum;

    if (list->size == 0)
    {
        list->head = new_node;
        list->tail = new_node;
    }
    else
    {
        new_node->next = list->head;
        list->head = new_node;
    }

    list->size++;
    return 1;
}

int singly_linked_list_push_back(singly_linked_list_t* list, int datum)
{
    singly_linked_list_node_t* new_node;

    if (!list)
    {
        return 0;
    }

    new_node = malloc(sizeof *new_node);

    if (!new_node)
    {
        return 0;
    }

    new_node->datum = datum;

    if (list->size == 0)
    {
        list->head = new_node;
        list->tail = new_node;
    }
    else
    {
        list->tail->next = new_node;
        list->tail = new_node;
    }

    list->size++;
    return 1;
}

int singly_linked_list_pop_front(singly_linked_list_t* list)
{
    int result;
    singly_linked_list_node_t* node;

    if (!list)
    {
        abort();
    }

    if (list->size == 0)
    {
        abort();
    }

    result = list->head->datum;
    node = list->head;
    list->head = list->head->next;
    list->size--;

    if (!list->head)
    {
        list->tail = NULL;
    }

    free(node);
    return result;
}

int singly_linked_list_pop_back(singly_linked_list_t* list)
{
    int result;
    singly_linked_list_node_t* current_node;
    singly_linked_list_node_t* previous_node;

    if (!list)
    {
        abort();
    }

    if (list->size == 0)
    {
        abort();
    }

    current_node = list->head;
    previous_node = NULL;

    while (current_node->next)
    {
        previous_node = current_node;
        current_node = current_node->next;
    }

    result = current_node->datum;

    if (!previous_node)
    {
        list->head = NULL;
        list->tail = NULL;
    }
    else
    {
        previous_node->next = NULL;
        list->tail = previous_node;
    }

    list->size--;
    free(current_node);
    return result;
}

size_t singly_linked_list_size(singly_linked_list_t* list)
{
    if (!list)
    {
        abort();
    }

    return list->size;
}

singly_linked_list_iterator_t*
singly_linked_list_get_iterator(singly_linked_list_t* list)
{
    singly_linked_list_iterator_t* iterator;

    if (!list)
    {
        return NULL;
    }

    iterator = malloc(sizeof *iterator);

    if (!iterator)
    {
        return NULL;
    }

    iterator->next_node = list->head;
    return iterator;
}

int singly_linked_list_iterator_has_next(singly_linked_list_iterator_t* iterator)
{
    if (!iterator)
    {
        abort();
    }

    return iterator->next_node != NULL;
}

int singly_linked_list_iterator_next(singly_linked_list_iterator_t* iterator)
{
    int result;

    if (!iterator)
    {
        abort();
    }

    if (!singly_linked_list_iterator_has_next(iterator))
    {
        abort();
    }

    result = iterator->next_node->datum;
    iterator->next_node = iterator->next_node->next;
    return result;
}

(Demo driver is here.)

A weakness of a singly-linked list is that we have to scan the entire list whenever popping the back in order to find the second last node. I suggest you use a doubly-linked list after all since it allows popping the back of the list in \$\Theta(1)\$.

Hey @coderodde, thanks for all the advices. The only question I have, is where would be a better place to define *pointerToLinkedList (which I will rename to list_head) and list_tail (which I will also implement)? Thanks! — Frankg26
– Frankg26, Commented Oct 1, 2017 at 15:47
@Frankg26 Sure. I have added the Advice 8 in order to answer your requested question. Thank you for your patience. — coderodde
– coderodde, Commented Oct 1, 2017 at 15:59
Thanks a lot @coderodde! And no worries, thank you for taking time to answer my questions! — Frankg26
– Frankg26, Commented Oct 1, 2017 at 16:02
@coderodded regarding Advice 8, what is the size_t type of size in the linked_list_t struct? Is this a placeholder for the size? Is Int a valid replacement for size_t? Thanks — Frankg26
– Frankg26, Commented Oct 1, 2017 at 16:07
I wouldn't add thattypedef stuff, since you pollute the namespace. Since the C language committee will probably never put user defined namespaces in the language despite it being possible to add with out breaking backwards compatibility, you'll actually have to worry about namespace conflicts, especially with a name like "node". For this reason you should actually prefer saying "struct node my_node" in contrast with "node my_node". If you do happen to have a namespace conflict here, it will be much more clear where it exists as well. — Krupip
– Krupip, Commented Oct 2, 2017 at 3:28

chux · Accepted Answer · 2017-10-02 14:51:12Z

Bugs, so not quite 100% functional.

Bug 1: Consider insertNodeEnd(42);. The following attempts to de-reference NULL. insertNodeEnd() appears to rely on the list having a prior insertion.

struct node *pointerToLinkedList = NULL;
...
struct node *secondLastNode = pointerToLinkedList;
while(secondLastNode->link != NULL){               // !! secondLastNode may be NULL

Bug 2: deleteHead() and deleteTail() have similar problems. Code should handle a deleteHead()/deleteTail() on an empty list.

void deleteHead(){
  struct node *temp = pointerToLinkedList;
  pointerToLinkedList = pointerToLinkedList->link;  // !! pointerToLinkedList may be NULL

Bug 3: (pedantic). Code lacks out-of memory detection and handling.

// struct node *newNode = (struct node*) malloc(sizeof(struct node));
struct node *newNode = malloc(sizeof *newNode);
// add
if (newNode == NULL) TBD_Code();

Am I using the free() function properly? Is the structure actually being removed from the dynamic memory?

Yes. Yes.

What other functions apart from the four currently installed, would you recommend to implement as an exercise?

void initList(void);  // restore to initial condition (empty the list)
unsigned ListLength(void);
bool ListEmpty(void);  // Is it empty?
bool deleteHead_Save_int(int *); // return success flag (was list not empty?)
bool deleteTail_Save_int(int *); // return success flag (was list not empty?)
bool getHead_Save_int(int *); // return success flag (was list not empty?)
bool getTail_Save_int(int *); // return success flag (was list not empty?)
void printList(FILE *stream, const char *prefix, const char *format, 
    const char *separator, const char *sufffix);
void IterateList(int (*f)(void *, int), void *state); // function on each list node's int

// advanced
void sortList(int (*f)(int,int));

... defining *pointerToLinkedList in a better spot.

Rather than support only 1 list, re-architect to support multiple lists.

Consider passing into each function, a pointer to an opaque list type and "hide" implementation details from the user of your functions. Develop a naming convention that begins with the function set's name.

typedef struct F26List_s *F26List;
some_return_type F26List_DoThis(F26List *list,  ...);
some_return_type F26List_DoThat(F26List *list,  ...);

[edit]

Re-architecture idea: Presently the single linked list has 4 operations to add to the head/tail and delete form the head/tail. Two of these take O(1) time and 2 of them take O(n) time. By having the tail node point to the head instead of NULL, 3 of these take O(1) time and 1 remains O(n) time. The other change is that rather than keeping track of the head node, code keeps track of the tail node as the head node is then tail->next. No need for a list structure with a head & tail pointer, just a tail pointer.

Thanks a lot for the reply @chux! So your suggestion regarding defining *pointerToLinkedList, is to use a struct (like I would use an object in Java) to have a blueprint of *pointerToLinkedList and then be able to create multiple lists? — Frankg26
– Frankg26, Commented Oct 1, 2017 at 15:52
@wizzwizz4 size_t is a good alternative. Note that a linked-list, unlike an array, is not limited to SIZE_MAX nor UINT_MAX, etc. nodes. size_t is a good compromise. — chux
– chux, Commented Oct 2, 2017 at 14:37

StoryTeller - Unslander Monica · Accepted Answer · 2017-10-01 07:35:19Z

5

Don't use globals. Currently you rely on the global pointerToLinkedList to be your list head. But that limits you to having only a single linked list. That isn't all the useful. A program may want to have several. It may want to split them, splice them, etc. You can't do that with your design.
You have a node type, but no list type. So to go towards having several lists in your program, like I said in #1, let's define one. Fortunately it's fairly simple. The usual abstraction is to just add something like this:
```
typedef struct node *list_t;
```
Now, don't be scared about the fact this hides pointer semantics. We want list_t to be an opaque "value type" of a list handle. The above will do.
To continue with #1 and #2, you should pass the list handle to the functions for modifications. I.e.
```
void insertNodeBeginning(list_t *list, int aData)
```
Note the single asterisk. We intend to modify the list. The list handle we design is a value. And we need to pass a pointer to it, in order to allow modification of the handle.
Casting the result of malloc is ill-adivsed. Also, don't repeat types so much. A simple newNode = malloc(sizeof *newNode); is correct for whatever pointer type.
Rather than have a "delete head" or "delete tail", try going for a "delete position" instead. More general means more uses for it. I.e:
```
void deleteAt(list_t *list, struct node* position)
```
That's not without a price, of course. You must verify the position belongs to the list. But it can also be done as part of looking for the previous node, that you need to preform the deletion.

edited Oct 1, 2017 at 7:35

answered Oct 1, 2017 at 6:49

StoryTeller - Unslander Monica

5464 silver badges12 bronze badges

\$\begingroup\$ Thanks @StoryTeller for the reply! Regarding #5, the parameter "struct node* position" refers to the address of the node that will be deleted? Am I correct? Also I do not really understand what you mean with #3. \$\endgroup\$

Frankg26
– Frankg26

2017-10-01 16:04:03 +00:00
Commented Oct 1, 2017 at 16:04
\$\begingroup\$ @Frankg26 - Yes in regard to #5. As for #3. When you want to change something, you need to pass a pointer to it. Modifying the list may require modifying the handle. We want the caller to see that modification. \$\endgroup\$

StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica

2017-10-01 16:05:27 +00:00
Commented Oct 1, 2017 at 16:05
\$\begingroup\$ Not everyone sees the value in the typedef, .e.g. Linus Torvalds. \$\endgroup\$

Kaz
– Kaz

2017-10-01 22:28:39 +00:00
Commented Oct 1, 2017 at 22:28
\$\begingroup\$ @StoryTeller I added version 2! In case you are curious! \$\endgroup\$

Frankg26
– Frankg26

2017-10-02 01:08:53 +00:00
Commented Oct 2, 2017 at 1:08
\$\begingroup\$ @Kaz - Um... did you read Linus' post carefully? He objects to a typedef that provides no abstration. I used it to create an opaque list handle. That's an abstraction. \$\endgroup\$

StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica

2017-10-02 04:14:53 +00:00
Commented Oct 2, 2017 at 4:14

Add a comment |

user149994 · Accepted Answer · 2017-10-01 10:02:39Z

If insertion/deletion at list end is a thing, you don't want to scan the list from the start each time. Once you keep track of a tail, it makes sense to have a separate list type different from just a pointer to the head. Something like:

struct node {
  struct node *next;
  ...
};

struct list {
  struct note *head, **tail;
};

void init_list (struct list *l)
{
  l->head = NULL;
  l->tail = &head;
}

void insert_at_front (struct list *l, struct node *new_node)
{
  new_node->next = l->head;
  l->head = new_node;
  if (l->tail == &l->head)
    l->tail = &new_node->next;
}

void insert_at_tail (struct list *l, struct note *new_node)
{
  new_node->next = *l->tail; /* or = NULL, but *l->tail can be useful */
  *l->tail = new_node;
  l->tail = &new_node->next;
}

and so on.

Hey @user149994, thanks for the reply! One question, why is the tail (**tail) in the struct list a pointer to a pointer? — Frankg26
– Frankg26, Commented Oct 1, 2017 at 15:57

pacmaninbw · Accepted Answer · 2017-10-01 13:16:50Z

0

@chux and @coderodde did a good job of covering the issues.

The function free() is being used correctly and it is deleting the memory.

The list in the implementation can't be sorted, because the nodes can't be inserted in the middle of the list. The implementation needs a general insertNode() function and a general deleteNode() function. The functions currently in the implementation handle the edge cases or special cases, they don't handle all cases of insertion or deletion. Inserting into the middle or deleting from the middle requires more interesting logic that will keep the linked list intact.

answered Oct 1, 2017 at 13:16

pacmaninbw♦

26.2k13 gold badges47 silver badges114 bronze badges

\$\begingroup\$ Thanks for the reply @pacmaninbw. Do you mean that rather than inserting/deleting at the beginning/end, I need a general method that incorporates the two of them? Or an additional method that allows insertion at the middle? \$\endgroup\$

Frankg26
– Frankg26

2017-10-01 15:56:13 +00:00
Commented Oct 1, 2017 at 15:56
\$\begingroup\$ You need a general method that incorporates the two of them as well as inserting into the middle. \$\endgroup\$

pacmaninbw
– pacmaninbw ♦

2017-10-02 16:05:58 +00:00
Commented Oct 2, 2017 at 16:05

Add a comment |

Stack Exchange Network

My linked list implementation in C

5 Answers 5

You must log in to answer this question.

Hot Network Questions

My linked list implementation in C

5 Answers 5

You must log in to answer this question.

Related

Hot Network Questions