Linked List implementation- Program crashing

Question

I was developing a generic linked list. Although the compiler doesn't give any error but on running the program, it just crashes. I haven't been able to figure out what's wrong but since I am trying insert method of the list in main, the problem is somewhere there itself. Here's the code in List.h

#include<cstdlib>

enum Error_code
{
    success,
    overflow,
    underflow,
    range_error
};

template<class Node_entry>
struct Node
{
    Node_entry entry;
    Node<Node_entry> *next;

    Node()
    {
        next=NULL;
    }

    Node(Node_entry item, Node<Node_entry> *add_on=NULL)
    {
        entry=item;
        next=add_on;
    }
};

template<class List_entry>
class List
{
  public:
    List()
    {
        count=0;
        head=NULL;
    }

    Error_code insert(int position, const List_entry &x)
    {
        if(position<0 || position>count)
            return range_error;
        Node<List_entry> *previous, *following, *new_node;
        if(position>0) {
            previous=set_position(position-1);
            following=previous->next;
        } else {
            following=head;
        }
        new_node = new Node<List_entry>(x, following);
        if(new_node==NULL)
            return overflow;
        if(position==0)
            head=new_node;
        else
            previous->next=new_node;
        count++;
        return success;
    }

    Error_code remove(int position, List_entry &x)
    {
        if(position<0 || position>count)
            return overflow;
        Node<List_entry> *old_node, *previous;
        if(position==0)
            old_node=head;
        else {
            previous=set_position(position-1);
            old_node=previous->next;
        }
        if(old_node==NULL)
            return underflow;
        if(position==0) {
            head=old_node->next;
            delete old_node;
        } else {
            previous->next=old_node->next;
            delete old_node;
        }
        count--;
        return success;
    }

    bool empty() const
    {
        return count==0;
    }

    ~List()
    {
        Node<List_entry> *temp_node=head->next;
        while(!empty()) {
            delete head;
            head=temp_node;
            temp_node=head->next;
        }
    }

  protected:
    int count;
    Node<List_entry> *head;

    Node<List_entry> *set_position(int position)const
    {
        Node<List_entry> *q=head;
        for(int i=0;i<count;i++)
            q=q->next;
        return q;
    }
};

main.cpp

#include <iostream>
#include"List.h"
using namespace std;
int main()
{
    int i;
    List<int> the_list;
    the_list.insert(1, 2);
}

P.S I am just into learning the basics for now and not working on large scale design modules and practices. At this point, this only needs to work.

It's not a good pratice to include "code" into the header file. Just put the prototypes into the header. — ykatchou
– ykatchou, Commented Jan 10, 2011 at 10:23
Its a generic implementation. If I make sepearate definition and code file, it gives an error. — Cipher
– Cipher, Commented Jan 10, 2011 at 10:24
Could you indent your code plz ? It's really not readable at all :( — ykatchou
– ykatchou, Commented Jan 10, 2011 at 10:26
@ykatchou: these are template classes, so the code needs to be in the header. — Fred Foo
– Fred Foo, Commented Jan 10, 2011 at 10:30
Btw: You insert an element in an empty list to the 2nd position (1st position: 0, 2nd position: 1) — phlipsy
– phlipsy, Commented Jan 10, 2011 at 10:30

Puppy · Accepted Answer · 2011-01-10 10:31:30Z

4

You set the head to NULL in the constructor, but don't check for null in any of your functions. In set_position, you blindly try to iterate through head and accompanying nodes without verifying that they actually exist.

answered Jan 10, 2011 at 10:31

Puppy

147k40 gold badges271 silver badges481 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

phlipsy Over a year ago

Especially in the destructor, derefencing head via head->next. That's the position where you get a SEGFAULT.

Puppy Over a year ago

@phlipsy: It's UB, since the OP doesn't specify his platform.

Fred Foo · Accepted Answer · 2011-01-10 10:38:59Z

1

What happens in your main function is:

Construct list; success.
Try to insert at position 1, which fails with range_error because position>count. If you choose to return error codes, you should always check for them.
Destroy list. This segfaults because head is NULL when you try to dereference it with Node<List_entry> *temp_node=head->next;

answered Jan 10, 2011 at 10:38

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

3 Comments

Cipher Over a year ago

Inadvertently, I made this list presuming the list is already populated. Can you please help me on how to initialize and populate the list for the first time?

Fred Foo Over a year ago

Put a check for head == NULL in the insert member and set head if true. Also check for NULL in other members, including the destructor, as @DeadMG suggests.

Cipher Over a year ago

I changed it but the crash problem is still there. Is this correct now? pastebin.com/fViVQKRK

Vilx- · Accepted Answer · 2011-01-10 10:34:36Z

1

Just to add to other answers - set_position method has a bug, it uses count instead of position.

answered Jan 10, 2011 at 10:34

Vilx-

107k93 gold badges294 silver badges432 bronze badges

Collectives™ on Stack Overflow

Linked List implementation- Program crashing

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related