06 April 2009

Doubly linked lists

I found it funny that I happened to read these two pages within days of each other.

A better way, developed by Bernard Greenberg in Multics EMACS and used in ZWEI, is to represent the buffer as a doubly-linked list containing pointers to strings, one for each line. Newline characters are not actually present, but implicitly appear after each line except the last.

—Richard Stallman
EMACS: The Extensible, Customizable Display Editor

On only one occasion have I used doubly linked lists, and it soon became clear that this was a mistake. This was when I tried to implement a simple text editor, with each line of text being a list item. This is the wrong approach because text is composed of characters, and newline characters should be treated, for most purposes, like any other character. Lists, doubly or singly linked, are not the right data structure here.

—Donald Fisk
Doubly Linked Lists

No comments: