lists.md

Lists

Table of contents

• General information
• Singly linked lists
• Doubly linked lists
  • XOR doubly linked lists
  • Circular lists
• Skip lists

---

General information

🔗

• Linked list – Wikipedia
• B.Stroustrup. Are lists evil? – B.Stroustrup’s FAQ
• K.Hedström. Number crunching: Why you should never, ever, ever use linked-list in your code again (2012)

🎥

• B.Stroustrup. Why you should avoid linked lists – Going Native (2012)
• S.Bagley. Arrays vs linked lists – Computerphile (2017)

📖

• Ch. 3: Linked lists – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

---

Singly linked lists

A singly linked list contains nodes which have a data field, and next field, which points to the next node in the list. In the C++ standard library a singly linked list is implemented in std::forward_list class template (also known as std::slist in some extensions before it was standardized). See std::forward_list – The standard library.

📖

• Sec. 3.1: Singly linked lists – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

📄

• Z.Shao, J.H.Reppy, A.W.Appel. Unrolling lists – ACM conference on LISP and functional programming, 185 (1994)

⚓

• std::forward_list – C++ reference

---

Doubly linked lists

A doubly linked list contains nodes which have a data field, and next and prev fields, which point to the next and to the previous nodes in the list, respectively. In the C++ standard library a doubly linked list is implemented in std::list class template. See std::list – The standard library.

🔗

• Doubly linked list – Wikipedia

📖

• Sec. 3.2: Doubly linked lists – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

⚓

• std::list – C++ reference

XOR doubly linked lists

📝

• If garbage collection is enabled, XOR linked list needs to declare its nodes reachable. For C++, see std::declare_reachable – C++ reference.

🔗

• XOR linked list – Wikipedia
• P.Sinha. A memory-efficient doubly linked list – Linux Journal

Circular lists

• Sec. 3.3: Circular lists – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

---

Skip lists

See Skip lists – Randomized algorithms and probabilistic data structures