The doubly-linked-list Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The doubly-linked-list Reference Manual

This is the doubly-linked-list Reference Manual, version 1.0.0, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:42:41 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

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

(ql:quickload :doubly-linked-list)

Usage

To create an empty doubly 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. It 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 doubly 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-2018 Michael Fiano.

Licensed under the MIT License.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 doubly-linked-list

Maintainer

Michael Fiano <mail@michaelfiano.com>

Author

Michael Fiano <mail@michaelfiano.com>

Home Page

https://www.michaelfiano.com/projects/doubly-linked-list

Source Control

(:git "git@github.com:mfiano/doubly-linked-list.git")

Bug Tracker

https://github.com/mfiano/doubly-linked-list/issues

License

MIT

Description

An implementation of the doubly linked list data structure.

Long Description

# 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

“‘ lisp
(ql:quickload :doubly-linked-list)
“‘

## Usage

To create an empty doubly 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:

“‘ lisp
(defparameter *dlist* (make-dlist))
“‘

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

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

“‘ lisp
(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:

“‘ lisp
(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:

“‘ lisp
(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:

“‘ lisp
(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 doubly linked list with some nodes, it would be nice to be able to search for a node. For this you use ‘FIND-NODE‘:

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

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

“‘ lisp
(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:

“‘ lisp
(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:

“‘ lisp
(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:

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

To get an association list mapping node keys to values:

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

## License

Copyright © 2015-2018 [Michael Fiano](mailto:mail@michaelfiano.com).

Licensed under the MIT License.

Version

1.0.0

Dependency

alexandria

Source

doubly-linked-list.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 doubly-linked-list.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/doubly-linked-list-20180228-git/doubly-linked-list.asd

Systems

doubly-linked-list (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 doubly-linked-list/package.lisp

Parent

doubly-linked-list (system)

Location

package.lisp

Packages

doubly-linked-list


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 doubly-linked-list/doubly-linked-list.lisp

Dependency

package.lisp (file)

Parent

doubly-linked-list (system)

Location

doubly-linked-list.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 doubly-linked-list

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Functions

Function: dlist-elements DLIST

Get an association list of node keys and values of DLIST.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: dlist-head INSTANCE
Function: (setf dlist-head) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: dlist-tail INSTANCE
Function: (setf dlist-tail) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: find-node DLIST KEY &key FROM-END

Find the first node in DLIST with the given KEY. If FROM-END is non-nil, then DLIST is searched in reverse, from end to start.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: make-dlist &key TEST

Create a new doubly linked list. TEST is a function used for comparing the keys of nodes.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: node-key INSTANCE
Function: (setf node-key) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: node-value INSTANCE
Function: (setf node-value) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: remove-node DLIST KEY &key FROM-END

Remove the first node found having KEY from DLIST. If FROM-END is non-nil, then DLIST is searched in reverse, from end to start.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: remove-nodes DLIST &rest KEYS

Remove all nodes from DLIST with the given KEYS.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Generic functions

Generic Function: insert-node WHERE DLIST KEY VALUE &key FROM-END TARGET-KEY &allow-other-keys

Insert a new node constructed from KEY and VALUE into DLIST. WHERE specifies where in DLIST to place the new node.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Methods
Method: insert-node (WHERE (eql after)) DLIST KEY VALUE &key FROM-END TARGET-KEY

Insert a new node constructed from KEY and VALUE into DLIST. The node is placed after the node having a key of TARGET-KEY. If FROM-END is non-nil, then DLIST is searched in reverse, from end to start.

Method: insert-node (WHERE (eql before)) DLIST KEY VALUE &key FROM-END TARGET-KEY

Insert a new node constructed from KEY and VALUE into DLIST. The node is placed before the node having a key of TARGET-KEY. If FROM-END is non-nil, then DLIST is searched in reverse, from end to start.

Method: insert-node (WHERE (eql tail)) DLIST KEY VALUE &key

Insert a new node constructed from KEY and VALUE into DLIST. The node is placed at the end of DLIST.

Method: insert-node (WHERE (eql head)) DLIST KEY VALUE &key

Insert a new node constructed from KEY and VALUE into DLIST. The node is placed at the beginning of DLIST.


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: %insert-node DLIST BEFORE AFTER KEY VALUE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: %make-dlist &key TEST
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: copy-dlist INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: copy-node INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: dlist-p OBJECT
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: dlist-test INSTANCE
Function: (setf dlist-test) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: make-node &key (KEY KEY) (VALUE VALUE) (PREVIOUS PREVIOUS) (NEXT NEXT)
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: node-next INSTANCE
Function: (setf node-next) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: node-p OBJECT
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: node-previous INSTANCE
Function: (setf node-previous) VALUE INSTANCE
Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Structures

Structure: dlist ()

A doubly linked list that holds sequential nodes with links to the previous and next node.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: head
Readers

dlist-head (function)

Writers

(setf dlist-head) (function)

Slot: tail
Readers

dlist-tail (function)

Writers

(setf dlist-tail) (function)

Slot: test
Readers

dlist-test (function)

Writers

(setf dlist-test) (function)

Structure: node ()

A doubly linked list node with references to the previous and next node in the list.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: key
Readers

node-key (function)

Writers

(setf node-key) (function)

Slot: value
Readers

node-value (function)

Writers

(setf node-value) (function)

Slot: previous
Readers

node-previous (function)

Writers

(setf node-previous) (function)

Slot: next
Readers

node-next (function)

Writers

(setf node-next) (function)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   D   F   L  
Index Entry  Section

D
doubly-linked-list.asd: The doubly-linked-list<dot>asd file
doubly-linked-list/doubly-linked-list.lisp: The doubly-linked-list/doubly-linked-list<dot>lisp file
doubly-linked-list/package.lisp: The doubly-linked-list/package<dot>lisp file

F
File, Lisp, doubly-linked-list.asd: The doubly-linked-list<dot>asd file
File, Lisp, doubly-linked-list/doubly-linked-list.lisp: The doubly-linked-list/doubly-linked-list<dot>lisp file
File, Lisp, doubly-linked-list/package.lisp: The doubly-linked-list/package<dot>lisp file

L
Lisp File, doubly-linked-list.asd: The doubly-linked-list<dot>asd file
Lisp File, doubly-linked-list/doubly-linked-list.lisp: The doubly-linked-list/doubly-linked-list<dot>lisp file
Lisp File, doubly-linked-list/package.lisp: The doubly-linked-list/package<dot>lisp file

Jump to:   D   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   %   (  
C   D   F   G   I   M   N   R  
Index Entry  Section

%
%insert-node: Internal functions
%make-dlist: Internal functions

(
(setf dlist-head): Exported functions
(setf dlist-tail): Exported functions
(setf dlist-test): Internal functions
(setf node-key): Exported functions
(setf node-next): Internal functions
(setf node-previous): Internal functions
(setf node-value): Exported functions

C
copy-dlist: Internal functions
copy-node: Internal functions

D
dlist-elements: Exported functions
dlist-head: Exported functions
dlist-p: Internal functions
dlist-tail: Exported functions
dlist-test: Internal functions

F
find-node: Exported functions
Function, %insert-node: Internal functions
Function, %make-dlist: Internal functions
Function, (setf dlist-head): Exported functions
Function, (setf dlist-tail): Exported functions
Function, (setf dlist-test): Internal functions
Function, (setf node-key): Exported functions
Function, (setf node-next): Internal functions
Function, (setf node-previous): Internal functions
Function, (setf node-value): Exported functions
Function, copy-dlist: Internal functions
Function, copy-node: Internal functions
Function, dlist-elements: Exported functions
Function, dlist-head: Exported functions
Function, dlist-p: Internal functions
Function, dlist-tail: Exported functions
Function, dlist-test: Internal functions
Function, find-node: Exported functions
Function, make-dlist: Exported functions
Function, make-node: Internal functions
Function, node-key: Exported functions
Function, node-next: Internal functions
Function, node-p: Internal functions
Function, node-previous: Internal functions
Function, node-value: Exported functions
Function, remove-node: Exported functions
Function, remove-nodes: Exported functions

G
Generic Function, insert-node: Exported generic functions

I
insert-node: Exported generic functions
insert-node: Exported generic functions
insert-node: Exported generic functions
insert-node: Exported generic functions
insert-node: Exported generic functions

M
make-dlist: Exported functions
make-node: Internal functions
Method, insert-node: Exported generic functions
Method, insert-node: Exported generic functions
Method, insert-node: Exported generic functions
Method, insert-node: Exported generic functions

N
node-key: Exported functions
node-next: Internal functions
node-p: Internal functions
node-previous: Internal functions
node-value: Exported functions

R
remove-node: Exported functions
remove-nodes: Exported functions

Jump to:   %   (  
C   D   F   G   I   M   N   R  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   H   K   N   P   S   T   V  
Index Entry  Section

H
head: Internal structures

K
key: Internal structures

N
next: Internal structures

P
previous: Internal structures

S
Slot, head: Internal structures
Slot, key: Internal structures
Slot, next: Internal structures
Slot, previous: Internal structures
Slot, tail: Internal structures
Slot, test: Internal structures
Slot, value: Internal structures

T
tail: Internal structures
test: Internal structures

V
value: Internal structures

Jump to:   H   K   N   P   S   T   V  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   D   N   P   S  
Index Entry  Section

D
dlist: Internal structures
doubly-linked-list: The doubly-linked-list system
doubly-linked-list: The doubly-linked-list package

N
node: Internal structures

P
Package, doubly-linked-list: The doubly-linked-list package

S
Structure, dlist: Internal structures
Structure, node: Internal structures
System, doubly-linked-list: The doubly-linked-list system

Jump to:   D   N   P   S