doubly-linked-list

2017-05-16

doubly-linked-list

An implementation of the doubly linked list data structure.

Overview

This system provides an implementation of the doubly linked list data structure, where a list holds sequential nodes, each having a link to the previous and next node.

Install

This system is not yet available to be installed automatically with Quicklisp. To manually install using Quicklisp, clone this repository into your local-projects directory and issue the following in your REPL:

(ql:quickload :doubly-linked-list)

Usage

To create an empty double linked list, use MAKE-DLIST. You can also specify the test function for comparing node keys, if the default #'EQL is not ideal. We will bind this to a global variable and reuse this object below for illustration purposes:

(defparameter *dlist* (make-dlist))

INSERT-NODE is used for creating and adding new nodes to the list. INSERT-NODE returns the node, not the list.

To add a new node to the front of the list:

(insert-node :head *dlist* :a 1) ; => #<NODE (:A 1)>
*dlist* ; => #<DLIST ((:A . 1))>

Note that any key may be used, provided the test function supplied to MAKE-DLIST is able to compare them (by default #'EQL). Also, any object may be used as a node's value.

To insert a new node to the end of the list:

(insert-node :tail *dlist* :b 2) ; => #<NODE (:B 2)>
*dlist* ; => #<DLIST ((:A . 1) (:B . 2))>

To insert a new node before another node in the list:

(insert-node :before *dlist* :c 3 :target-key :b) ; => #<NODE (:C 3)>
*dlist* ; => #<DLIST ((:A . 1) (:C . 3) (:B . 2))>

To insert a new node after another node in the list:

(insert-node :after *dlist* :d 4 :target-key :a) ; => #<NODE (:D 4)>
*dlist* ; => #<DLIST ((:A . 1) (:D . 4) (:C . 3) (:B . 2))>

Now that you have a double linked list with some nodes, it would be nice to be able to search for a node. For this you use FIND-NODE:

(find-node *dlist* :a) ; => #<NODE (:A 1)>

If we were to add a node with a duplicate key:

(insert-node :tail *dlist* :a 'duplicate) ; => #<NODE (:A DUPLICATE)>

Using FIND-NODE on the list now would still return the node having a value of 1. This is because the search starts from the front of the list, and returns as soon as it finds a node with a matching key as compared by the test function of the list. Instead we can search in reverse, that is, starting from the tail and searching backwards. For this we can use the optional :FROM-END argument:

(find-node *dlist* :a :from-end t) ; => #<NODE (:A DUPLICATE)>

:FROM-END can also be supplied to INSERT-NODE when inserting with :BEFORE or :AFTER.

To remove a node in the list:

(remove-node *dlist* :a :from-end t) ; => #<NODE (:A DUPLICATE)>
*dlist* ; => #<DLIST ((:A . 1) (:D . 4) (:C . 3) (:B . 2))>

To remove all nodes in the list with the given keys:

(remove-nodes *dlist* :a :b :c) ; => #<DLIST ((:D . 4))>
*dlist* ; => #<DLIST ((:D . 4))>

To get an association list mapping node keys to values:

(dlist-elements *dlist*) ; => ((:D . 4))

License

Copyright ? 2015 Michael Fiano .

Licensed under the MIT License.

A copy of the license is available here.

Author
Michael Fiano <michael.fiano@gmail.com>
Maintainer
Michael Fiano <michael.fiano@gmail.com>
License
MIT