Adt lab/linked lists

This is part of adt lab

List nodes

typedef

In C++, you can simply declare a new type based on known types using typedef.

typedef int valueType;

valueType x = 10;

We will declare new valueType so that our linked list code works fairly well with any types. We will eventually use template to make generic linked list.

struct

struct ListNode
{
  valueType val;
  ListNode* next;

  ListNode(valueType val, ListNode* next=0)
    : val(val), next(next) {}
};

Linked list class

typedef int valueType;

struct ListNode
{
  valueType val;
  ListNode* next;

  ListNode(valueType val, ListNode* next=0)
    : val(val), next(next) {}
};

class LinkedList
{
private:
  ListNode* header;
  void free_list();

public:
  LinkedList();
  ~LinkedList();
  void print_list();
  void insert_front(valueType x);
};

LinkedList::LinkedList()
{
  header = new ListNode(0);
}

LinkedList::~LinkedList()
{
  free_list();
}

void LinkedList::print_list()
{
  ListNode* node = header->next;
  while(node != 0) {
    cout << node->val << endl;
    node = node->next;
  }
}

void LinkedList::insert_front(valueType x)
{
}

void LinkedList::free_list()
{
}

Copy constructor

You can't pass an object of class LinkedList that we have written by value to other functions. For example, if you write

void test(LinkedList l)
{
  l.append(1000);
}

main()
{
  LinkedList l1;

  test(l1);
  
  l1.append(10);
}

When you run your program, you may get this run-time error:

*** Error in `./a.out': double free or corruption (fasttop): 0x0000000002138010 ***

This happens because the destructor has been called twice: once for l1 and another for its copy l in function test. However, its copy, by default, was created by copying every data members of l1, i.e., its header and tail pointers point to the same location as of l1. When the list l was destroyed, its destructor also destroyed the original list data.

To prevent this problem, you can pass l1 by reference as in the next code. In this case l and l1 is the same list.

void test(LinkedList& l)
{
  l.append(1000);
}

main()
{
  LinkedList l1;

  test(l1);
  
  l1.append(10);
}

But if you want l and l1 to be different lists, you need to implement its copy constructor yourself. (Read more at copy constructor's article at wikipedia)