Linked lists - Buffering

Linked lists

Linked lists are a way of combining buffers in a regular and methodical way using pointers to point to the next entry in the list. The linking is maintained by adding an entry to a buffer which contains the address to the next buffer or entry in the list. Typi-cally, other information such as buffer size may be included as well as allowing the list to support different size entries. Each buffer will also include information for its control such as next data pointers and water marks depending on their design or construction.

With a single linked list, the first entry will use the pointer entry to point to the location of the second entry and so on. The last entry will have a special value which indicates that the entry is the last one.

New entries are added by breaking the link, extracting the link information and then inserting the new entry and remaking the link. When appending the entry to the end, the new entry pointer takes the value of the original last entry — the end of list special value in this case. The original last entry will update its link to point to the new entry and in this way the link is created.

The process for inserting in the middle of the list is shown in the diagram and follows the basic principles.

Linked lists have some interesting properties. It is possible to follow all the links down to a particular insertion point. Please note that this can only be done from the first entry down without storing additional information. With a single linked list like the one shown, there is no information in each entry to show where the link came from, only where it goes to. This can be overcome by storing the link information as you traverse down the list but this means that any search has to start at the top and work through, which can be a tiresome process.

The double linked list solves this by using two links. The original link is used to move down and the new link contains the missing information to move back up. This provides a lot more flexibility and efficiency when searching down the list to deter-mine an entry point. If a list is simply used to concatenate buffers or structures together, then the single link list is more than ad-equate. If the ability to search up and down the list to reorder and sort the list or find different insertion points, then the double linked list is a better choice to consider.