3. Linked Lists

Doubly linked lists

0 of 5 activities0%

Reading 1

Two directions

Open

A doubly linked node has next and prev. You can walk either way and delete a node in O(1) if you already hold its pointer (after fixing neighbors).

Tradeoff: extra memory per node and more pointer updates on insert/delete.

Useful for deques and LRU-cache style structures.

struct DNode {
  int data;
  DNode* next;
  DNode* prev;
};

Check 2

Open

Compared to singly linked lists, doubly linked nodes add

Fill in 3

Open

Try it 4

Open

Print forward then back.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Same as length: read n and n ints into a doubly linked list conceptually; print n (length).

main.cpp

Loading editor…