Singly linked list Tail

Question

if you want create a singly linked list like this:

struct Node { 
    int data;
    Node *next;
};

struct List{ 
    Node *head;
    // Node *tail; --> necessary?
    Node *last;
};

And this list has the methods "append", "remove", "printList" and "findElement". Is it necessary to have a tail? Because with "last" you can address the last node.

So when it is necessary to have all three Nodes "head", "tail" and "last"? When you want to insert the node sorted into the list for example?

Answer 1

No, it's not necessary. The tail is equal to head->next and thus it would be redundant and add bookkeeping overhead to keep this field updated.

Also note that the field last is kind of unusual. In most use cases, you add elements to the head of a singly linked list and use a different data structure when you really need to add to the end.

Answer 2

Actually, you can implement enqueue (append at tail), push (prepend at head), dequeue (remove from head), and of course find and print with with a one-pointer header. The trick is to make the list circular and have the header point to the tail. Then tail->next is the head.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_s {
  struct node_s *next;
  int data;
} Node;

typedef struct list_s {
  Node *tail;
} List;

Node *new_node(int data) {
  Node *node = malloc(sizeof *node);
  node->data = data;
  node->next = node;
  return node;
}

void init_list(List *list) {
  list->tail = NULL;
}

int is_empty(List *list) {
  return list->tail == NULL;
}

void enqueue(List *list, Node *node) {
  if (list->tail) {
    Node *head = list->tail->next;
    node->next = head;
    list->tail->next = node;
    list->tail = node;
  } else list->tail = node->next = node;
}

void push(List *list, Node *node) {
  if (list->tail) {
    Node *head = list->tail->next;
    node->next = head;
    list->tail->next = node;
  } else list->tail = node->next = node;
}

Node *dequeue(List *list) {
  Node *head = list->tail->next;
  if (head == list->tail)
    list->tail = NULL;
  else
    list->tail->next = head->next;
  return head;
}

void print_list(List *list) {
  printf("The list:\n");
  if (list->tail) {
    Node *head = list->tail->next;
    Node *p = head;
    do {
      printf("%d\n", p->data);
      p = p->next;
    } while (p != head);
  }
}

int main(int argc, char *argv[]) {
  List list[1];
  init_list(list);

  // Build the list in order and print it.
  for (int i = 0; i < 4; i++) enqueue(list, new_node(i));
  print_list(list);

  // Remove elements from head until empty.
  printf("Dequeueing:\n");
  while (!is_empty(list)) {
    Node *node = dequeue(list);
    printf("%d\n", node->data);
    free(node);
  }

  // Build the list in reverse order and print it.
  for (int i = 0; i < 4; i++) push(list, new_node(i));
  print_list(list);

  return 0;
}

Answer 3

I think it depends on what operations you want to use.

1. Assuming you want to insert and delete nodes at the tail of a list, it is certainly a wise choice to keep a last node in your list.

2. Otherwise, if you want to do operations at the beginning of the list, a last node is unnecessary.

Answer 4

It's not necessary but a tail can be useful if you're working with the linked list in a queue-like FIFO fashion rather than a stack-like LIFO fashion or want to be able to transfer entire lists of elements from one head to another's tail without disrupting the relative order of the elements.

Note that I'm referring to 'tail' as a reference to the last node in the list which I believe is safe to assume that the question is about.

A lot of very micro-optimized SLL implementations often are tail-less and work like a stack while backed by an efficient fixed allocator for locality of reference (cache-friendliness) and faster node allocations/deallocations. There the primary benefit of the SLL over a variable-sized array-based sequence is the ability to start moving things around by just changing the value of the next pointer/reference and the lack of invalidation on inserting/removing elements if you're working in native, lower-level languages that involve pointers. The lack of a tail can boost performance quite a bit by reducing the amount of branching instructions required in operations to push and pop from the stack.

For the needs you listed, whether the tail is going to help or just add unnecessary complexity and overhead is if your append and remove operations can work strictly from the front in a LIFO stack fashion or if you want to be able to append to the back but remove from the front in a FIFO fashion without any iteration involved, e.g. If you don't have a tail in the latter case, one of these operations are going to go from constant-time complexity to linear-time complexity, and you might improve your use cases by exchanging that linear-time algorithmic complexity for the relatively smaller micro-level overhead of maintaining a tail.