In a language like JavaScript, to create a Linked List, you can do this:

class Node() {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}

var LL1 = new Node(1, new Node(2, new Node(3, new Node(4, null))));

What is nice about this for interviews is that you don't have to keep track of when you need to free memory.

With an example of something similar in C :

template<typename T>
struct Node {
  Node() = delete;

  Node(const T value, Node<T> *next)
  : value(value), next(next) {};

  T value;
  Node<T> *next;
}

int main(int argc, char *argv[]) {
  Node<int> *LL1 = new Node<int>(1, new Node<int>(2, new Node<int>(3, new Node<int>(4, nullptr))));

  return 0;
}

I'm not properly freeing the memory here.

Is there a way I can write my Node class so that I don't have to keep references to new Node<T>s in order to delete them later?

The only way I know of doing it is like so:

int main(int argc, char *argv[]) {
  Node<int> *node4 = new Node<int>(4, nullptr);
  Node<int> *node3 = new Node<int>(3, node4);
  Node<int> *node2 = new Node<int>(2, node3);
  Node<int> *LL1 = new Node<int>(1, node2);

  delete node4;
  delete node3;
  delete node2;
  delete LL1;

  return 0;
}

CodePudding user response：

Is there a way I can write my Node class so that I don't have to keep references to new Node<T>s in order to delete them later?

Yes - you could use (in this example, a fixed sized) array to hold the Node objects with automatic storage duration, so they get destroyed automatically at program exit. Then simply link the Nodes together before using them, eg:

#include <iostream>

template<typename T>
struct Node {
  Node() = default;

  Node(const T &value, Node<T> *next = nullptr)
    : value(value), next(next) { }

  T value{};
  Node<T> *next = nullptr;
};

int main() {
  Node<int> nodes[4];

  Node<int> *node4 = &nodes[3];
  *node4 = Node<int>(4);
  Node<int> *node3 = &nodes[2];
  *node3 = Node<int>(3, node4);
  Node<int> *node2 = &nodes[1];
  *node2 = Node<int>(2, node3);
  Node<int> *LL1 = &nodes[0];
  *LL1 = Node<int>(1, node2);

  /* alternatively:

  Node<int> *next = nullptr;
  for(int i = 3; i >= 0; --i) {
    nodes[i] = Node<int>(i 1, next);
    next = &nodes[i];
  }

  Node<int> *LL1 = &nodes[0];
  */

  // use LL1 as needed...

  return 0;
}

Online Demo

Online Demo

CodePudding user response：

If you're writing C for real (as in for a real job), then you should always use RAII. Failure to do so is often considered equivalent to a bug in practice, and will make you look bad in an interview.

Nobody ever really makes a linked list class, but if you have to for an interview, and you want to use Nodes as lists in client code, then you should arrange for each node to own the next node. Destroying a node should automatically clean up anything that it owns.

In modern C , we don't have to remember to delete stuff anymore.

You should also make sure that destroying a node doesn't recurse into the destructors for all the next nodes, because a linked list on the heap may have enough nodes to overflow the stack.

template<typename T> class Node {
  public:
  Node(const T &value, std::unique_ptr<Node<T>> &&next)
    : value(value), next(next) { }
  ~Node() {
    // delete the chain iteratively to avoid stack overflow
    while (next) {
      // this assignment deletes the node that next points to
      // and replaces it with the following node.
      next = next->detach_next();
    }
  }
  Node<T> *get_next() const {
    return next.get();
  }
  std::unique_ptr<Node<T>> detach_next() {
    std::unique_ptr<Node<T>> ret(std::move(next));
    next.reset();
    return ret;
  }
  const T &get_value() const {
    return value;
  }
  T &get_value() {
    return value;
  }

  private:
  T value;
  std::unique_ptr<Node<T>> next;
};

You can then make and use your list like this:

int main(int argc, char *argv[]) {
  std::unique_ptr<Node<int>> list;
  list.reset(new Node<int>(4,std::move(list));
  list.reset(new Node<int>(3,std::move(list));
  list.reset(new Node<int>(2,std::move(list));
  list.reset(new Node<int>(1,std::move(list));

  for (Node<int> *n = list.get(); n; n = n->get_next()) {
    std::cout << n->get_value() << std::endl;
  }
  //everything gets cleaned up here
  return 0;
}