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 and assignment operator

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 to handle object copy. (Read more at copy constructor's article at wikipedia)

Another case when default copying operation does not work is when you use assignments, as in:

  LinkedList l1, l2;

  l2 = l1;

In C++, Rule of three states that if you implement any of these methods, you should implement all three:

• destructor
• copy constructor
• copy assignment operator

The following shows the code for copy constructor and copy assignment operator for our LinkedList class.

class LinkedList
{
// ...
  
public:
  LinkedList();
  LinkedList(const LinkedList& list);

  // ...
  LinkedList& operator=(const LinkedList& list);
};

LinkedList::LinkedList(const LinkedList& list)
{
  header = new ListNode(0);
  tail = header;
  ListNode* p = list.header->next;
  while(p != 0) {
    append(p->val);
    p = p->next;
  }
}

LinkedList& LinkedList::operator=(const LinkedList& list)
{
  if(this != &list) {
    free_list();
    header = new ListNode(0);
    tail = header;
    ListNode* p = list.header->next;
    while(p != 0) {
      append(p->val);
      p = p->next;
    }
  }
}

Copy-and-swap idiom

Read at stackoverflow.

Here is a new version of the assignment operator using the copy-and-swap idiom.

class LinkedList
{
// ...
public:
  // ...
  LinkedList& operator=(LinkedList list);

  void swap(LinkedList& l1, LinkedList& l2);
};

void LinkedList::swap(LinkedList& l1, LinkedList& l2)
{
  std::swap(l1.header, l2.header);
  std::swap(l1.tail, l2.tail);
}

LinkedList& LinkedList::operator=(LinkedList list)
{
  swap(*this, list);
  return *this;
}