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.3 "Robert April" on Tue Feb 20 08:35:09 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. 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 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 Michael Fiano michael.fiano@gmail.com.

Licensed under the MIT License.

A copy of the license is available here.


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 <michael.fiano@gmail.com>

Author

Michael Fiano <michael.fiano@gmail.com>

Home Page

https://github.com/mfiano/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. ‘INSERT-NODE‘ 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 Michael Fiano <michael.fiano@gmail.com>.

Licensed under the MIT License.

A copy of the license is available [here](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/quickbuilder/quicklisp/dists/quicklisp/software/doubly-linked-list-20171019-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)

Nickname

dll

Use List
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 in the given doubly linked list.

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 a doubly linked list with the given key.
If FROM-END is non-nil, then the double linked list is searched in reverse, from end to start.

Package

doubly-linked-list

Source

doubly-linked-list.lisp (file)

Function: make-dlist &key (HEAD HEAD) (TAIL TAIL) (TEST TEST)
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 with the given key from a doubly linked list.
If FROM-END is non-nil, then the doubly linked list 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 a doubly linked list 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

Create and insert a new node into a doubly linked list.

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 into a doubly linked list after the given target key’s node.
If FROM-END is non-nil, then the doubly linked list 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 into a doubly linked list before the given target key’s node.
If FROM-END is non-nil, then the doubly linked list is searched in reverse, from end to start.

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

Insert a new node at the end of a doubly linked list.

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

Insert a new node at the start of a doubly linked list.


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

Low-level function for inserting a new node into a doubly linked list.

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
Initform

(function eql)

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

(
(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, (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