[Operator Overloading]Doubly Linked List

子车飞文

2023-12-01

Introduction

We are going to design a link list class in c++. Again, the knowledge of pointer in c++ is widely used this time and you have to focus when you are coding.

Knowledge

This time, you are going to finish a advanced list which is known as doubly linked list. Each node of the list have three members: data which is use as the real storage, next pointer which is used to linked the next node of the list, prev pointer which is use to linked the previous node.

![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked- list.svg/610px-Doubly-linked-list.svg.png)

Requirements

Finish the member functions below.

Notice that for output functions, the format is as below:

toString() [1,2,3,4,5]
NULL<-1<->2<->3<->4<->5->NULL
toString() []
NULL
toString() [1]
NULL<-1->NULL
No new line is needed;

void split(int position, list* des1, list* dest2) 2 [1,2,3,4]
[1,2] [3,4]

list& merge(const list& src1, const list& src2) [1,2,3,4] [5,6,7,8]
[1,2,3,4,5,6,7,8]

list& remove_if(bool (*condition)(listPointer)); [1,2,3,4,5,6] condition =
odd number

[2,4,6]

list& unique(void) [1,2,2,3,4,4,5,6]
[1,2,3,4,5,6]

list& reverse(void) [1,2,3,4,5,6]

[6,5,4,3,2,1]

Links

Auto repair tool for annoying Google style:

传送门

clang-format -i -style=Google CODE_FILES
出题人：叶嘉琪 (已毕业多年老TA，大家怨念不要太深，如有问题欢迎邮件)讨论）

main.cpp

#include "List.hpp"
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

bool condition1(list::listPointer p) { return true; }

bool condition2(list::listPointer p) {
  if (p->data % 2 == 0) {
    return false;
  }
  return true;
}

bool condition3(list::listPointer p) {
  if (p->data > 5) {
    return false;
  }
  return true;
}

void outputList(const list& li) {
  cout << li << " size:" << li.size();
  if (&li.front() == NULL) {
    cout << " front:NULL";
  } else {
    cout << " front:" << li.front();
  }

  if (&li.back() == NULL) {
    cout << " back:NULL";
  } else {
    cout << " back:" << li.back();
  }
  cout << endl;
}

int main() {
  int n, m;

  cin >> n >> m;

  int* a = new int[n]();

  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  if (true) {
    list li1(a, n);

    li1.insert(2, 111);
    li1.push_front(150);
    list li2(li1);
    outputList(li1);
    outputList(li2);
  }

  cout << endl;

  if (true) {
    list li1;
    for (int i = 0; i < n; i++) {
      li1.insert(i, a[i]);
    }
    for (int i = 0; i < m; i++) {
      li1.erase(i);
    }
    outputList(li1);
  }

  cout << endl;

  if (true) {
    list li1(a, n), li2, li3;
    li1 = li2 = li3 = li1;
    outputList(li1);
    li1.split(0, &li2, &li3);
    outputList(li1);
    outputList(li2);
    outputList(li3);
    li1.split(li1.size(), &li2, &li3);
    outputList(li1);
    outputList(li2);
    outputList(li3);
    li1.split(li1.size() / 2, &li2, &li3);
    cout << li2.toString() << endl;
    cout << li3.toString() << endl;
    li1 += (li2 += li1).merge(li1, li1);
    outputList(li1);
    li1 += li3;
    li2.merge(li1, li3);
    for (int i = 0; i < li1.size(); i++) {
      cout << li1[i] << " ";
    }
    cout << endl;
    outputList(li2);
  }

  cout << endl;

  cout << endl;

  if (true) {
    list li1(a, n);
    li1.remove_if(condition1);
    cout << li1 << " " << endl;
    li1.assign(a, n);
    li1.remove_if(condition2);
    cout << li1 << endl;
    li1.assign(a, n);
    li1.remove_if(condition3);
    outputList(li1);
  }

  cout << endl;

  if (true) {
    list li(a, n);
    li.merge(li, li).merge(li, li).unique();
    outputList(li);
  }

  delete[] a;

  return 0;
}

List.hpp

#ifndef LIST
#define LIST

#include <string>
#include <iostream>

class list {
 public:
  typedef int data_type;
  struct node {
   public:
    data_type data;
    node* next;
    node* prev;
    node(data_type data = 0, node* next = NULL, node* prev = NULL)
        : data(data), next(next), prev(prev){};
  };
  typedef node listNode;
  typedef node* listPointer;
  typedef unsigned int size_type;

 private:
  listPointer head;
  listPointer tail;
  size_type _size;
  inline listPointer at(int index) {
    if (index >= 0 && index < this->_size) {
      if (index <= this->_size / 2) {
        int counter = 0;
        listPointer p = this->head;
        while (counter != index) {
          counter++;
          p = p->next;
        }
        return p;
      } else {
        int counter = 0;
        listPointer p = this->tail;
        while (counter != this->_size - 1 - index) {
          counter++;
          p = p->prev;
        }
        return p;
      }
    }
    return NULL;
  }

 public:
  list();
  // construct a list from an exist array
  list(const data_type[], int length);
  list(const list&);
  list& operator=(const list&);
  ~list();

  // Capacity
  bool empty(void) const;
  size_type size(void) const;

  // Element access
  data_type& front(void) const;
  data_type& back(void) const;

 public:
  // output
  std::string toString(void) const;

  // Modifiers
  void assign(const list&);
  void assign(const data_type datas[], int length);
  void push_front(const data_type&);
  void push_back(const data_type&);
  void pop_front(void);
  void pop_back(void);

  void insert(int position, const data_type& data);
  void erase(int position);
  void clear(void);

  // Operations
  // split this list into to lists at the given position
  void split(int position, list* des1, list* dest2);
  // merge two list to this list from src1 and src2
  list& merge(const list& src1, const list& src2);
  // remove the elements who satisfy the condition
  list& remove_if(bool (*condition)(listPointer));

  // remove duplicate elements
  list& unique(void);
  // reverse the list
  list& reverse(void);

  // operators
  data_type& operator[](int index);
  list& operator+=(const list&);
  friend std::ostream& operator<<(std::ostream& os, const list& li);
};

#endif

List.cpp

#include "List.hpp"
#include <string>
#include <sstream>
#include <assert.h>
#include <exception>

void list::clear() {
  listPointer p = this->head;
  listPointer q = NULL;
  // 不要在循环里面定义q。因为这样内存消耗较大，每次都要定义一个q。
  while (p != NULL) {
    q = p;
    p = p->next;
    delete q;
  }
  this->head = NULL;
  this->tail = NULL;
  this->_size = 0;
  // head要回到初始化。
}

list::list() {
  this->head = this->tail = NULL;
  this->_size = 0;
}

list::list(const list& another) {
  this->head = this->tail = NULL;
  this->_size = 0;
  // 先初始化！再进行复制！
  this->assign(another);
}

list::list(const data_type datas[], int length) {
  this->head = this->tail = NULL;
  this->_size = 0;
  // 再说一遍！先初始化，在复制！
  this->assign(datas, length);
}

list& list::operator=(const list& another) {
// 此处不用初始化是因为*this对象已经被初始化了，清空的操作在assign中完成。
    this->assign(another);
    return *(this);
}

list::~list() { this->clear(); }

bool list::empty() const { return this->_size == 0; }

list::size_type list::size() const { return this->_size; }

list::data_type& list::front() const {
  return this->empty() ? *reinterpret_cast<data_type*>(NULL) : head->data;
}
/* reinterpret_cast<type-id> (expression)
type-id 必须是一个指针、引用、算术类型、函数指针或者成员指针。它可以把一个指针转换成一个整数，也可以把一个整数转换成一个指针（先把一个指针转换成一个整数，再把该整数转换成原类型的指针，还可以得到原先的指针值）。*/
// 在此处，如果链表是空，就返回一个NULL指针。


list::data_type& list::back() const {
  return this->empty() ? *reinterpret_cast<data_type*>(NULL) : tail->data;
}

inline std::string int2String(int a) {
  std::stringstream ss;
  ss << a;
  return ss.str();
}
/* 在tostring中会经常使用到整数转换为string类型，在这里定义为inline类型可以节省函数调用的开销，而且简化代码。*/

std::string list::toString(void) const {
  if (this->_size == 0) {
    return "NULL";
  }
  std::string ret;
  listPointer p = this->head;
  ret += "NULL<-";
  while (p != NULL) {
    ret += int2String(p->data);
    if (p != this->tail) {
      ret += "<->";
    }
    p = p->next;
  }
  ret += "->NULL";
  return ret;
}
// 重载了两个assign。 
void list::assign(const list& another) {
  if (!(this == &another)) {
  // 如果左值和右值相同，则不操作。
    this->clear();
    node* p = another.head;
    while (p != NULL) {
      this->push_back(p->data);
      p = p->next;
    }
  }
}

void list::assign(const data_type datas[], int length) {
  this->clear();
  for (int i = 0; i < length; i++) {
    this->push_back(datas[i]);
  }
}

void list::push_front(const data_type& data) {
  this->insert(0, data);
  assert(this->head->data == data);
  // 断言！如果没有插入成功，程序自动停止。方便代码维护。
}

void list::push_back(const data_type& data) {
  this->insert(this->_size, data);
  assert(this->tail->data == data);
}

void list::pop_front(void) { this->erase(0); }

void list::pop_back(void) { this->erase(this->_size - 1); }

void list::insert(int position, const data_type& data) {
  if (position == 0) {
    listPointer temp = new listNode(data, this->head);
    this->head = temp;
    assert(this->head != NULL);
    if (this->_size == 0) {
      this->tail = this->head;
    } else {
      this->head->next->prev = head;
    }
    this->_size++;
  } else if (position == this->_size) {
    listPointer temp = new listNode(data, NULL, this->tail);
    this->tail->next = temp;
    this->tail = this->tail->next;
    this->_size++;
  } else {
    listPointer p = at(position - 1);
    if (p != NULL) {
      listPointer temp = new listNode(data, p->next, p);
      p->next->prev = temp;
      p->next = temp;
      this->_size++;
      assert(this->at(position)->data == data);
    }
  }
}

void list::erase(int position) {
  if (this->empty()) return;
  if (position == 0) {
    if (this->_size == 1) {
      delete this->head;
      this->tail = this->head = NULL;
    } else {
      assert(head->next != NULL);
      this->head = this->head->next;
      delete this->head->prev;
      this->head->prev = NULL;
      /* 被delete掉的指针都要给定NULL。如果还要用到的话，例如head/tail的相关指针，因为被删除内存后，可能会指向系统内任意一个地址。*/
      this->_size--;
    }
  } else if (position == this->_size - 1) {
    this->tail = this->tail->prev;
    assert(tail != NULL);
    delete this->tail->next;
    this->tail->next = NULL;
    this->_size--;
  } else {
    listPointer p = at(position);
    if (p != NULL) {
      p->prev->next = p->next;
      p->next->prev = p->prev;
      delete p;
      this->_size--;
    }
  }
}

void list::split(int position, list* dest1, list* dest2) {
  if (dest1 == dest2) {
    throw dest1;
    return;
  }
  if (position < 0 || position > this->_size) return;
  listPointer p = this->head;
  int counter = 0;
  list temp1, temp2;
  while (p != NULL) {
    if (counter == position) {
      break;
    }
    temp1.push_back(p->data);
    p = p->next;
    counter++;
  }
  while (p != NULL) {
    temp2.push_back(p->data);
    p = p->next;
  }
  // 赋值操作符。
  (*dest1) = temp1;
  (*dest2) = temp2;
}

list& list::merge(const list& src1, const list& src2) {
  list temp;
  if (src1.empty()) {
    temp = src2;
  } else {
    temp = src1;
    listPointer p = src2.head;
    while (p != NULL) {
      temp.push_back(p->data);
      p = p->next;
    }
  }
  *(this) = temp;
  return *(this);
}

list& list::remove_if(bool (*condition)(list::listPointer)) {
  listPointer p = this->head;
  while (p != NULL) {
    if (condition(p)) {
      if (p == this->head) {
        this->head = this->head->next;
        if (this->head != NULL) {
          this->head->prev = NULL;
        }
        delete p;
        this->_size--;
        p = this->head;
        if (p == NULL) {
          this->tail = NULL;
        }
      } else if (p == this->tail) {
        this->tail = this->tail->prev;
        this->tail->next = NULL;
        delete p;
        this->_size--;
        p = NULL;
      } else {
        p->prev->next = p->next;
        p->next->prev = p->prev;
        listNode* q = p->next;
        delete p;
        p = q;
        this->_size--;
      }
    } else {
      p = p->next;
    }
  }
  return *(this);
}

list& list::unique(void) {
  listPointer slow, fast;
  slow = this->head;
  while (slow != NULL) {
    fast = slow->next;
    while (fast != NULL) {
      if (fast->data == slow->data) {
        if (fast == this->head) {
          this->head = this->head->next;
          if (this->head != NULL) {
            this->head->prev = NULL;
          } else {
            this->tail = NULL;
          }
          fast = this->head;
        } else if (fast == this->tail) {
          this->tail = this->tail->prev;
          this->tail->next = NULL;
          delete fast;
          fast = NULL;
        } else {
          fast->next->prev = fast->prev;
          fast->prev->next = fast->next;
          listPointer temp = fast;
          fast = fast->next;
          delete temp;
        }
        this->_size--;
      } else {
        fast = fast->next;
      }
    }
    slow = slow->next;
  }
  return *(this);
}
/* 提供一个非指针操作。*/
/*
list& list::unique() {
    for (int i = 0; i != _size; i++) {
        for (int j = i + 1; j != _size; j++) {
            if (this->operator[](i) == this->operator[](j)) {
                erase(j);
                j--;
            }
        }
    }
    return *this;
}
*/

list& list::reverse(void) {
  listPointer p = this->head;
  while (p != NULL) {
    listPointer q = p->prev;
    p->prev = p->next;
    p->next = q;
    p = p->prev;
  }
  listPointer q = this->tail;
  this->tail = this->head;
  this->head = q;
  return *(this);
}

list::data_type& list::operator[](int index) {
  listPointer p = at(index);
  assert(p != NULL);
  return p->data;
}

list& list::operator+=(const list& another) {
  return this->merge(*this, another);
}

std::ostream& operator<<(std::ostream& os, const list& li) {
  return (os << li.toString());
}