a heap-use-after-free wrong in the question--Design MyLinkList (LeetCode No.707)

Question

Below is my C code for LeetCode no. 707 "Design Linked List":

typedef struct MyLinkedList{
    int val;
    struct MyLinkedList *next;
} MyLinkedList, *LinkList;


MyLinkedList* myLinkedListCreate() {
    LinkList p = (LinkList)malloc(sizeof(MyLinkedList));
    p->val = 0;
    p->next = NULL;
    return p;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    int i = 0;
    LinkList p = obj;
    while(p != NULL){
        if(i == index) return p->val;
        else{
            p = p->next;
            i++;
        }
    }
    return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList *new = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    new->val = val;
    new->next = obj;
    obj = new;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList *tail = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    tail->next = NULL;
    tail->val = val;
    LinkList p = obj;
    while(p->next != NULL){
        p = p->next;
    }
    p->next = tail;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    MyLinkedList *node = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    node->val = val;
    LinkList p = obj;
    for(int i = 0; i != index - 1; i++){
        p = p->next;
    }
    if(p == NULL) return;
    node->next = p->next;
    p->next = node;
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    LinkList p = obj;
    int i = 0;
    if(index < 0) return ;
    if(index == 0){
        LinkList q = obj;
        obj = obj->next;
        free(q);
        return ;
    }
    while(i != index - 1){
        p = p->next;
    }
    LinkList q;
    q = p->next;
    p->next = p->next->next;
    free(q);
}

void myLinkedListFree(MyLinkedList* obj) {
    LinkList p = obj;
    while (p) {
        LinkList q = p;
        p = p->next; //maybe this line wrong
        free(q);
    }
}

The problem's code template explains that the solution will be exercised like so:

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/

When I run the LeetCode tests, I get this error:

==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000718 at pc 0x55b42a509da3 bp 0x7fffa049ff00 sp 0x7fffa049fef0

What is the bug in my code?

Answer 1

I'll think I dwell on the data-structure, rather than the implementation. There are lots of good advices in the above answers. In pseudo-code, a singly linked list should consist of:

List {
   Node head;
}

Where head signifies the start of the list. In order to traverse the list, a Node will need to know what succeeds it. And so:

Node {
    Node next;
    char[] key; // Could be whatever.
}

And thus, all we need to pass is the current head to traverse the list:

Node search(List list, char[] key) {
    Node node = list.head;
    while (node != null) {
        if (node.key == key) {break;}
        node = node.next;
    }
    return node; // Edge case, we did not find the key, i.e. node == null.
}

And with a singly linked list, inserting an item is just as easy:

void insert_start(List list, Node node) {
    node.next = list.head;
    list.head = node;
}

This pushes the existing items down the chain of the list. If you were to traverse the list from head to end, this would effectively be a stack. You could also choose to do the reverse, inserting at the end, it does however require us to traverse the list:

void insert_end(List list, Node node) {
    Node now = list.head;
    while (now.next != null) {
        now = now.next;
    }
    now.next = node;
}    

In this case, if you were to traverse the list from head to end, it would effectively be a queue. Now, for mutating the list, we practically do the same as we did when we inserted at the end of the list. However, instead of keeping track of when the list ends, we keep track of when index were mutating is the next:

void insert_at_index(List list, int idx, Node node) {
    Node now = list.head;
    int i = 0;
    while (++i < idx) {
        now = node.next;
    }
    // At this point now == the previous node than the index we're looking for,
    // granted that idx < length of list, i.e. edge case.
    node.next = now.next;
    now.next = node;
}

Deletion is similar:

void delete_at_index(List list, int idx) {
    Node now = list.head;
    int i = 0;
    while (++i < idx) {
        now = node.next;
    }
    // At this point now == the previous node than the index we're looking for,
    // granted that idx < length of list, i.e. edge case.
    Node tmp = now.next;
    now.next = tmp.next;
    // deallocate the node here (free(tmp)).
}

You may have noticed that we do an awful many traversals. Some clever guys noticed that too, and introduced doubly linked lists:

List {
   Node head;
   Node tail;
}

However now Node needs to also know what precedes it. Thus:

Node {
    Node next;
    Node prev;
}

With that we can insert at the end of the list in constant time, just as with insertion at the beginning:

void insert_start(List list, Node node) {
    list.tail.next = node;
    list.tail= node;
}

It may seem insignificant (at least I think so), but if you now kept track of the middle point of the list, you could insert/delete at an index, by backtracking from the middle point if the index is lower than the middle point, or the opposite if it's higher. Good luck on your leetcode.

Answer 2

For starters the function myLinkedListCreate does not make sense. Initially the pointer to the head node should be equal to NULL. That is to create a new empty list you can just write:

MyLinkedList *head = NULL;

Moreover the allocation of a node within the function:

MyLinkedList* myLinkedListCreate() {
    LinkList p = (LinkList)malloc(sizeof(MyLinkedList));
    p->val = 0;
    p->next = NULL;
    return p;
}

can fail. In this case these statements:

    p->val = 0;
    p->next = NULL;

will invoke undefined behavior. And it is unclear why an empty list contains a node with the stored value 0. Otherwise you will always need to skip this node in the list in other functions that deal with the list. And you will need to free memory for an empty list that sounds very strange.

The design of the function myLinkedListGet is very bad. The value -1 returned by the function in case when there are less nodes in the list than the specified index can be a valid value stored in a node. In such a case you will not know whether it is a valid value or a signal that a node is not found.

The function should be declared and defined the following way:

int myLinkedListGet( const MyLinkedList *head, size_t index, int *value ) 
{
    while ( head != NULL && index != 0 )
    {
        head = head->next; 
        --index;
    }

    if ( head != NULL ) *value = head->val;

    return head != NULL;
}

The function can be called like

MyLinkedList *head = NULL;

//...

int value = 0;
size_t index = some_value;

if ( myLinkedListGet( head, index, &value ) )
{
   // do something with the stored value in the variable value
}

Pay attention to that the first parameter of the function (the pointer to the head node) is declared with the qualifier const because the list itself it not changed within the function.

The declaration of the function myLinkedListAddAtHead is incorrect. Firstly the pointer to the head node is passed to the function by value. It means that the function deals with a copy of the value of the pointer to the head node. Changing the copy within the function like:

obj = new;

does not change the original pointer to the head node passed to the function. It stays unchanged that results in a memory leak. And secondly the function does not report whether memory for the new node was allocated or not. And again if the new node was not created these statements:

new->val = val;
new->next = obj;

will invoke undefined behavior.

You need to pass the pointer to the head node to the function by reference. In C passing by reference means passing an object (that in turn can be a pointer) indirectly through a pointer to it. Thus dereferencing the passed pointer within the function you can get a direct access to the original object.

The function can be declared and defined the following way:

int myLinkedListAddAtHead( MyLinkedList **head, int value ) 
{
    MyLinkedList *new_node = malloc( sizeof( MyLinkedList ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->val = value;
        new_node->next = *head;
        *head = new_node;
    }

    return success;
}

Alternatively you could for all functions that add new nodes to the list return a pointer to the head node that can be modified within functions (for example when the list is empty). But it is also not a good design because it is much better when functions return either success or failure of the operation of adding a new node to the list.

The same problems exist for the function myLinkedListAddAtTail. Pay attention to that if you are going to add new nodes to the tail of the list the list should be defined as a doubly-linked list.

The function myLinkedListAddAtIndex that has sinilar drawbacks as the functions described above that add new nodes to the list also can invoke undefined behavior in this for loop:

for(int i = 0; i != index - 1; i++){
    p = p->next;
}

because the specified index can be much greater than the number of nodes in the list. In this case a null pointer will be used in this statement

    p = p->next;

The same problems exist in the function myLinkedListDeleteAtIndex.

Pay attention to that the function myLinkedListFree also does not change the original pointer to he head node that can confuse users of the list. It would be again better to pass the pointer to the head node to the function by reference. That is the function can look the following way:

void myLinkedListFree( MyLinkedList **head ) 
{
    while ( *head ) 
    {
        MyLinkedList *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}     

And the function is called like:

MyLinkedList *head = NULL;
//...
myLinkedListFree( &head );

After calling this function the original pointer to the head node will be changed to NULL. That is the list indeed will be empty.

So in my opinion, for a beginner, the function declarations and their designs at leetCode are bad and incorrect relative to the C programming language.

Answer 3

The biggest issue is that the MyLinkedList, as implemented, is a node and not a list

There should be two separate structs, one for a node and one for a list [of nodes] (As hinted at in the last paragraph of John's answer).

From the linked problem:

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

A careful reading of this implies that the list does not have next and val--the node does. It is describing the node struct and not [anything] about the list struct.

Further all the subsequent descriptions of member functions imply that the list and node are separate (e.g.):

void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

In addition, looking at the code block on the right of the LeetCode page, we have a function definition of:

void myLinkedListAddAtHead(MyLinkedList* obj, int val)

The only [sane] way to implement this is with two different structs. (See below for more on this [*]).

IMO, part of the problem statement is a slight deception. It talks about the contents of a node but not of the list. It expects us to deduce that the correct/best solution is two structs.

Thus, we want (showing the doubly linked list case):

// element/node of linked list
typedef struct node MyNode;
struct node {
    int val;                            // node value
    MyNode *next;                       // pointer to next node in list
    MyNode *prev;                       // pointer to previous node in list
} MyNode;

// list of elements/nodes
typedef struct {
    MyNode *head;                       // pointer to first node in list
    MyNode *tail;                       // pointer to last node in list
} MyLinkedList;

---

Here is the full code based on the changed struct definitions. It (only) implements the singly linked case.

It is based off the example code from the LeetCode link. I changed obj into list to be more descriptive.

Note that things are much easier to code [and understand] if we use a for loop instead of a while loop when traversing the list.

It is coded and compiles (but it is not tested). It is annotated:

#include <stdlib.h>

// element/node of linked list
typedef struct node MyNode;
struct node {
    int val;                            // node value
    MyNode *next;                       // pointer to next node in list
    MyNode *prev;                       // pointer to previous node in list
};

// list of elements/nodes
typedef struct {
    MyNode *head;                       // pointer to first node in list
    MyNode *tail;                       // pointer to last node in list
} MyLinkedList;

// myLinkedListCreate -- create a new list
MyLinkedList *
myLinkedListCreate(void)
{
    MyLinkedList *list = calloc(1,sizeof(*list));

    return list;
}

// newnode -- create a new node
static MyNode *
newnode(int val)
{
    MyNode *add = calloc(1,sizeof(*add));

    if (add == NULL)
        exit(1);

    add->val = val;

    return add;
}

// myLinkedList:
// * get the value of the index'th node in the linked list
// * If the index is invalid, return -1
int
myLinkedListGet(MyLinkedList *list, int index)
{
    MyNode *cur = list->head;

    // find the nth node
    int idxcur = 0;
    for (;  cur != NULL;  cur = cur->next, ++idxcur) {
        if (idxcur == index)
            break;
    }

    return (cur != NULL) ? cur->val : -1;
}

// myLinkedListAddAtHead:
// * Add a node of value val before the first element of the linked list
// * After the insertion, the new node will be the first node of the linked
//   list
void
myLinkedListAddAtHead(MyLinkedList *list, int val)
{
    MyNode *add = newnode(val);

    add->next = list->head;
    list->head = add;
}

// myLinkedListAddAtTail:
// * Append a node of value val as the last element of the linked list
void
myLinkedListAddAtTail(MyLinkedList *list, int val)
{
    MyNode *add = newnode(val);

    // find the tail of the list
    MyNode *cur = list->head;
    MyNode *prev = NULL;
    for (;  cur != NULL;  cur = cur->next)
        prev = cur;

    // add to tail of list
    if (prev != NULL)
        prev->next = add;

    // add to empty list
    else
        list->head = add;
}

// myLinkedListAddAtIndex:
// * Add a node of value val before the indexth node in the linked list
// * If index equals the length of the linked list, the node will be appended
//   to the end of the linked list.
// * If index is greater than the length, the node will not be inserted.
void
myLinkedListAddAtIndex(MyLinkedList *list, int index, int val)
{
    MyNode *cur = list->head;
    MyNode *prev = NULL;

    int idxcur = 0;
    for (;  cur != NULL;  cur = cur->next, ++idxcur) {
        if (idxcur == index)
            break;
        prev = cur;
    }

    // is the index valid?
    // NOTE: at this point, idxcur is (either):
    // (1) an exact match
    // (2) the count of the nodes
    if (index <= idxcur) {
        MyNode *add = newnode(val);

        // add to tail of list
        if (prev != NULL)
            prev->next = add;

        // add to empty list
        else
            list->head = add;
    }
}

// myLinkedListDeleteAtIndex:
// * Delete the index'th node in the linked list, if the index is valid
void
myLinkedListDeleteAtIndex(MyLinkedList *list, int index)
{
    MyNode *cur = list->head;
    MyNode *prev = NULL;

    // find the nth node
    int idxcur = 0;
    for (;  cur != NULL;  cur = cur->next, ++idxcur) {
        if (idxcur == index)
            break;
        prev = cur;
    }

    // if we got a match
    if (cur != NULL) {
        // removing a non-head node
        if (prev != NULL)
            prev->next = cur->next;

        // removing the head node
        else
            list->head = cur->next;

        // free up the node
        free(cur);
    }
}

void
myLinkedListFree(MyLinkedList *list)
{

    MyNode *cur = list->head;
    MyNode *next;

    // remove all nodes from the list
    for (;  cur != NULL;  cur = next) {
        next = cur->next;
        free(cur);
    }

    // destroy the list
    free(list);
}

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 * myLinkedListAddAtHead(obj, val);
 * myLinkedListAddAtTail(obj, val);
 * myLinkedListAddAtIndex(obj, index, val);
 * myLinkedListDeleteAtIndex(obj, index);
 * myLinkedListFree(obj);
*/

---

[*] That's not totally true.

We could treat the first argument to the member functions as a pointer to a dummy node (as John mentioned). Then, we'd only need one struct. This is almost what you have already.

But, that is less type safe as we could [mistakenly] pass a true node pointer (with data) in as the list pointer (which has to have no data).

IMO, a degenerate case of trying to shoehorn list functionality into a node struct. That is, in the above code, we'd replace all instances of list->head with list->next (which can lead to confusion).

As an aside ...

I've heard that some companies use LeetCode problems to screen candidates (yecch!).

However, given this, if I were the hiring manager (and I've been one in the past), I would expect the candidate to read between the lines and come up with the two struct solution.

The slight vagueness of the problem description here is closer to a real world situation where I would want the candidate to find the better/best [thinking out of the box] solution.

Answer 4

Your struct MyLinkedList details are somewhat poorly suited to the required API. Note well that some of your list modification functions can remove the list's head node or insert another node before it, but you don't have a good way to convey back to the caller the change of head node. In particular, C has (only) call by value semantics, so assignments to function parameters, such as myLinkedListAddAtHead()'s

    obj = new;

do not produce an effect that is visible to the caller. The error likely arises from the tester calling myLinkedListDeleteAtIndex() to delete the node at index 0, after which the caller's pointer to the erstwhile list head is no longer valid.

There are two general approaches to that kind of problem:

• the linked list functions could return a pointer to the head node, which the caller will afterward use as the list head.

• the the list head pointer could be passed to list functions indirectly, either via a double pointer or inside another object to which a pointer is passed.

The function signatures you are required to implement do not do the first, nor do they provide for the double-pointer alternative of the second. Thus, you're left with the function arguments pointing to a structure that itself contains the head pointer, rather than pointing to the head pointer itself.

For that sort of arrangement, I ordinarily use a separate structure for representing nodes than for the overall list. That gives a representation of the overall list that is distinct from the representations of nodes, which facilitates things such as maintaining a head pointer in addition to a tail pointer. But you don't have to go that far. You could instead use one struct MyLinkedList as a dummy head node -- one that does not store an actual value, but instead serves only to hold a pointer to the real head node. Your myLinkedListCreate() function is already structured as if you were doing that, but your other functions don't match in that regard.

Answer 5

You have many logical errors.

For example when you delete node at index 0 your head is still referencing the same node which was already freed.

Adding at head also does not modify the the remembered head.

It is because void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) obj is a local variable and assigning it does not change the passed pointer,

You need to pass pointer to pointer void myLinkedListDeleteAtIndex(MyLinkedList **obj, int index) to modify the original passed pointer holding the head of the linked list.,

Same all other functions.

example:

void myLinkedListAddAtHead(MyLinkedList **obj, int val) {
    MyLinkedList *new = malloc(sizeof(*new));
    if(new)
    {
       new->val = val;
       new->next = *obj;
       *obj = new;
    }
}

You also never check the result of "malloc". Do not cast the return value of malloc. If the code does not compile it means that you use C++ compiler to compile C code - and it is not correct.

I would also suggest to check if passed pointers are not NULL.