The structure of a singly linked list has at least the following variation points: Programming the Logic Theory Machine (Newell and Shaw, 1957) describes algorithms for construction of linked lists and contains an early appearance of the the diagram showing linked elements. You can see in this survey of list processing languages from 1963 mentions these behavioral variants. There is also something similar called a “tail queue” but I believe that this is usually doubly linked.įrom what I can tell, the idea of a singly linked list and a “tail queue” have been around since the 50s. A tail-pointer variant provides all the functionality of an singly linked list but also allows constant-time insertion at the back of the list (but not constant time deletion at the back).It can be used as a push-down (LIFO) stack but doesn’t provide constant-time access to the tail. Singly linked list provides accesses all elements via the front of the list.The other also allows insertion at the back: One provides access only via the front/head of the list. I have made a poster to try to summarize everything visually. But you will notice that I am biased towards C and C++.Īlso note that although I have focused on the data structures here - the choice of structure is largely dictated by the algorithms and behavioral requirements. Mostly I try to refer to data structures, not implementations. If you know a data structures book (or survey paper) that does a better job of enumerating and analyzing all the variants please let me know - I’d like to read it. Links to additional resources are welcome. If you notice that I’ve missed a variant or a key point please let me know in the comments. I would like to document as many linked list variants as I can find in as concise a form as possible. circular linkage, null terminator, sentinel terminator) but I could not find a survey that clearly presented all the variants. When I decided to write this page it seemed as though every data structure book I opened presented a slightly different variant of the singly linked list (e.g. This is not a linked list tutorial - for that please check the links at the end. This page is intended as a compact survey of singly linked list variants. “Despite this obvious simplicity, there are myriad implementation variations.”
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |