I am writing my own implementation of a single linked list. I wrote a popBack() method, but it seems to me that it is too overloaded with conditional operators, which should affect performance (and in general, it looks so-so). Is it possible to optimize it somehow so that it does not look so terrible?

void popBack() {
  if (head == nullptr) {
    return;
  }
  if (head->next == nullptr) {
    delete head;
    head = nullptr;
  }
  else {
    Node* prev = nullptr;
    Node* curr = head;
    while(curr->next != nullptr) {
      prev = curr;
      curr = curr->next;
    }
    if(prev != nullptr) {
      delete curr;
      prev->next = nullptr;
    }
  }
  size--;
}

CodePudding user response：

The 2nd if block is not necessary. Also, the else block can be simplified if you use a Node** pointer to point at the Node* variable which needs to be null'ed when the Node object it is pointing at is delete'd, eg:

void popBack() {
  if (!head) return;
  Node *curr = head, **prev = &head;
  while (curr->next) {
    prev = &(curr->next);
    curr = *prev;
  }
  *prev = nullptr;
  delete curr;
  --size;
}

Of course, if you really want to optimize the popping, you should implement a double-linked list instead, and add a tail member to your list class to point at the last Node in the list, then you won't need a while loop to hunt for the trailing Nodes in the list, eg:

void popBack() {
  if (!tail) return;
  Node *curr = tail;
  tail = tail->previous;
  Node **n = (tail) ? &(tail->next) : &head;
  *n = nullptr;
  delete curr;
  --size;
}

CodePudding user response：

One technique that can clean the code up a lot is to ensure the list always includes one node that you basically treat as empty. You never use the value it contains, but it eliminates many of the corner cases, so most of the code never had to deal with them.

Using this, pop_back can end up something like this:

void pop_back() {
    if (head->next == nullptr)
        return; // empty list--nothing to do.

    // traverse to just before the sentinel node:
    node* loc;
    for (loc = head; loc->next->next != nullptr; loc = loc->next)
        ;

    // at this point, `loc` points to the last "real" node in the list
    // delete the old sentinel node
    // then turn this into the sentinel node by setting its next pointer
    // to a null pointer:
    delete loc->next;
    loc->next = nullptr;
}

Of course, to make this work, we have to assure the list always contains the sentinel node:

    LinkedList() {
        // node with its next pointer set to a null pointer:
        head = new node(nullptr);
    }

...and (of course) push_back has to be aware of the sentinel as well:

void push_back(T t) {
    if (head->next == nullptr) {
        head = new node(t, head);
        return;
    }

    node* loc;
    for (loc = head; loc->next->next != nullptr; loc = loc->next)
        ;

    loc->next = new node(t, loc->next);
}

We can also carry this a step further by saving the location of the sentinel node. Although we still need to traverse the list to do a pop_back, we can avoid it when we want to do a push_back (we put the new value into the current sentinel node, then allocate a new sentinel node, and update our tail pointer to its location.

This general approach is, however, restricted to types that we don't mind creating a default-constructed item that we don't (currently) use. In my experience that's true a lot more often than not, but there are exceptions for which this design isn't suitable.