Linked-list implementation

Question

Can anyone check and see if there is an error with my linked-list implementation? I keep getting a seg fault while trying to iterate through the linked list.

I'm trying to iterate through the linked list from the "root" in "process_command" but when I try to access root->child, I'll get a seg fault error.

Implementation of the node

typedef struct _node {
    struct _node *child;
    char *command;
} Command_list;

The two functions that I'm using to tokenize a string and put them into a linked-list.

Command_list *process_command( char command_line[256] )
{
    printf("Command: %s", command_line);

    //allocate space for root & child 
    Command_list *root = (Command_list*)malloc(sizeof (Command_list));
    Command_list *child = (Command_list*)malloc(sizeof (Command_list));

    char *token;
    char *saveptr;
    //get the first part of the string
    token = strtok_r( command_line, " ", &saveptr);

    //if the first word in the string is student
    if( !strcmp(token, "student") )
    {
        //set the first word to the be root
        root = insert_command( token, root );
        printf("Current root command: %s \n", root->command);
        child = root;

        //get the next word from the string
        token = strtok_r( NULL, " ", &saveptr);

        //keep getting words from the list and store them in a linked-list
        while( token != NULL )
        {
            child = insert_command( token, child );
            token = strtok_r( NULL, " ", &saveptr);
        }
    }
    return root;
}

Command_list *insert_command( char *value, Command_list *root)
{
    printf("previous value: %s \n", root->command);

    Command_list *child_node = (Command_list*)malloc(sizeof (Command_list));

    //if the node being passed in is empty, store the value in itself
    if( root->command == NULL ){
        root->command = value;
        root->child = 0;
        printf("Inserting value to root: %s \n", root->command);
        return root;
    }
    //otherwise store the value in a child node
    else
    {
        child_node->command = value;
        child_node->child = 0;
        printf("Inserting value to child node: %s \n", child_node->command);
        return child_node;
    }
}

EDIT: Iteration code

{
    ....
    Command_list *temp = (Command_list*)malloc(sizeof (Command_list));
    temp = root;
    while(temp != NULL){
    printf("Command: %s\n", temp->command);
    temp = temp->child;
    .... 
}

Added the iteration code that I'm using. The code seems to work fine in code-blocks but it stops iterating after the first output in the terminal.

Most likely not your problem, here, but don't cast the return of `malloc`, in general don't cast at all unless you know what you are doing: http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc — Jens Gustedt, Sep 30 '12 at 06:38
The compiler sees you're casting the return value of `malloc()` and punishes you. — , Sep 30 '12 at 06:41
There doesn't seem to be a segfault anymore. The code also seems to run perfectly fine in code blocks but not in the terminal. While in the terminal, it only iterates once and quits without any errors. — rlhh, Sep 30 '12 at 06:58

enhzflep · Accepted Answer · 2012-09-30T07:27:56.073

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

struct node
{
 node *next;
 char *command;
};

void addNode(node **listHead, char *newData)
{
    node *newNode;

    if (*listHead == NULL)
    {
        *listHead = (node*)malloc(sizeof(node));
        newNode = *listHead;
    }
    else
    {
        newNode = *listHead;
        while (newNode->next != NULL)
            newNode = newNode->next;
        newNode->next = (node*)malloc(sizeof(node));
        newNode = newNode->next;
    }
    newNode->next = NULL;
    newNode->command = strdup(newData);
}

node *makeLinkedListOfWords(char *inputString)
{
    char *token;
    char *cmdClone;
    char *delims = " ";
    node *result = NULL;

    cmdClone = strdup(inputString);
    token = strtok(cmdClone, delims);
    while (token != NULL)
    {
        addNode(&result, token);
        token = strtok(NULL, delims);
    }
    free(cmdClone);        // EDIT: forgot to give back the duplicate string's memory
    return result;
}


void printList(node *list)
{
    int i = 0;
    while (list != NULL)
    {
        printf("%d. '%s'\n", ++i, list->command);
        list = list->next;
    }
}

int main(int argc, char *argv[])
{
    node *list1 = makeLinkedListOfWords("this is a test");
    node *list2 = makeLinkedListOfWords("so is this");
    node *list3 = makeLinkedListOfWords("and this is another");
    printList(list1);
    printList(list2);
    printList(list3);
    return 0;
}

[EDITED: SO was turning this output into an ordered list, numbered 1-11 :grrr: )

Output:

1. 'this'
2. 'is'
3. 'a'
4. 'test'
1. 'so'
2. 'is'
3. 'this'
1. 'and'
2. 'this'
3. 'is'
4. 'another'

simonc · Answer 2 · 2012-09-30T07:51:02.427

When you allocate Command_list, you don't initialise its members. The test (root->command == NULL) in insert_command will then strictly speaking have undefined results. In all likelihood, this test will then fail and you'll go on to create a child node. Later calls to insert_command will add to a list that has this child node as its root.

Your iteration code will start from root which has uninitialised command and child. If printing command doesn't fail, moving to the child element and printing it almost certainly will.

Fixing this should fix your seg fault. You also have some memory leaks which could be tidied up:

The struct allocated for child near the top of process_command
child_node in insert_command in the case where root->command == NULL
The Command_list allocated in your iteration code

score -1 · Answer 3 · edited Nov 16 '16 at 20:43

template<class T>
ostream& operator<<(ostream& os, LinkedList<T>& ll) {
    if(!(ll.isEmpty()))
    {
        //os<<temp->data;
        int size=ll.size();
        int count=0;
        while(count<size)
        {
            os<<ll.get(count);
            if(count+1<size)
                os<<",";
            count++;
        }
    }
    else
    {
        os<<"[]";
    }

}

template<class T>       
LinkedList<T>::LinkedList(){
    head=NULL;
}

template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& other){
    this->head=0;
    Node<T>* tempHead=other.getLeader();
    while(tempHead!=0)
    {
        Node<T> *temp = new Node<T>(tempHead->data);
        temp->next = 0;
        Node<T>* curr = this->getLeader();
        if (curr != 0)
        {
            while (curr->next != 0)
            {
            curr = curr->next;
            }
            curr->next = temp;
        }
        else
        {
            this->head = temp;
        }
        tempHead=tempHead->next;
    }
}

template<class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& other){
    if(&other != this)
    {
        this->head=0;
        Node<T>* tempHead=other.head;
        while(tempHead!=0)
        {
            Node<T>* temp = new Node<T>(tempHead->data);
            temp->next = 0;
            Node<T>* curr = this->head;
            if (curr != 0)
            {
                while (curr->next != 0)
                {
                curr = curr->next;
                }
                curr->next = temp;
            }
            else
            {
                this->head = temp;
            }
            tempHead=tempHead->next;
        }
    }
    return *this;   


template<class T>
LinkedList<T>* LinkedList<T>::clone() {

    LinkedList<T>* list=new LinkedList<T>(*this);
    return list;

}

template<class T>
LinkedList<T>::~LinkedList(){

    Node<T>*temp;
    while (head != NULL)
    {
    temp = head->next;
    delete head;
    head = temp;
    }
}

template<class T>
void LinkedList<T>::insert(int index, T data){

    Node<T> *n= new Node<T>(data);
    if((0 <= index) &&( index<= size()))
    {
        if(index==0)
        {
            if(isEmpty())
            {
                head=n;
            }
            else
            {
                Node<T>*skip=head;
                head=n;
                head->next=skip;
            }
        }
        else
        {
            Node<T> *temp =head;
            int count =1;
            while(count!=index)
            {
                temp=temp->next;
                count++;
            }
            n->next=temp->next;
            temp->next=n;
        }
    }
    else
    {
        throw ("invalid index");
    }
    return ;
}   

template<class T>
T LinkedList<T>::remove(int index){
        T pet;
    if(0 <= index && index<= size()-1)
    {
        if(!isEmpty())
        {
            Node<T> *ret=getLeader();
            Node<T>* skip=NULL;
            if(index!=0)
            {
            int i=1;
            while(i!=(index))
            {
                ret=ret->next;
                i++;
            }
            skip=ret;
            pet=get(index);
            ret=ret->next;
            if(ret->next==NULL)
            {
                delete ret;
                skip->next=NULL;
                ret=NULL;
            }
            else
            {
                skip->next=ret->next;
                delete ret;
                ret=NULL;
            }
        }
        else
        {
                Node<T> *tmp = head->next;
                pet=get(index);
                delete head;
                head = tmp;
        }
        return pet;
        }
        else
        {  
            throw ("empty list");
        }

    }
    else
    {
        throw ("invalid index");
    }}


template<class T>   
T LinkedList<T>::get(int index) const {
    if(head!=NULL)
    {
        if(0 <= index && index<= size()-1)  
        {
            int count=0;
            Node<T>* place =head;
            while(place!=NULL)
            {
                if(count==index)
                {
                    return place->data;
                }
                count++;
                place=place->next;
            }
    }
        else
        {
          throw ("invalid index");
        }
    }
    else
    {
        throw("empty list");
    }
}

template<class T>
bool LinkedList<T>::isEmpty(){
    if(head==0)
    {
        return true ;
    }
    else
    {
        return false;
    }
}

template<class T>
void LinkedList<T>::clear(){
    Node<T>*temp=head;
    while(head!=NULL)
    {
        head=head->next;
        delete temp;
        temp=head;
    }
}   

template<class T>
Node<T>* LinkedList<T>::getLeader() const{
    return head;
}

template<class T>
ostream& LinkedList<T>::print(ostream& os){ 
    os<<*this;
}

template<class T>
int LinkedList<T>::size() const {
    int count=0;
    Node<T> *temp =getLeader();
    while(temp!=NULL)
    {
        temp=temp->next;
        count++;
    }
    return count;
}

template<class T>
T LinkedList<T>::operator[](int index){
    return get(index);
}

template<class T>
LinkedList<T>& LinkedList<T>::operator+(const LinkedList<T>& other){
    LinkedList<T>* ting=new LinkedList<T>(*this);
    Node<T>* UGE=other.getLeader();
    int count=ting->size();
    int pos=0;
    while(UGE!=NULL)
    {
        ting->insert(count,other.get(pos));
        UGE=UGE->next;
        pos++;
        count++;
    }
    return *ting;
}

Please post only the content relevant to answer the question. — skrtbhtngr, Nov 16 '16 at 18:58

Linked-list implementation

3 Answers3