Class: DoubleLinkedList

• Inheritance
• Description
• Instance protocol
  • adding & removing
• Examples

Inheritance:

   Object
   |
   +--Collection
      |
      +--SequenceableCollection
         |
         +--LinkedList
            |
            +--DoubleLinkedList

Package:

stx:libbasic2

Category:

Collections-Linked

Version:

rev: 1.3 date: 2023/01/31 21:15:28

user: cg

file: DoubleLinkedList.st directory: libbasic2

module: stx stc-classLibrary: libbasic2

Description:

this class implements an anchor to a list of DoubleLinks aka a double linked list.
The data itself is held in the link elements.
See (the abstract) DoubleLink, ValueDoubleLink and (possibly other) classes,
which can be used as elements of a double linkedList.

Please read the comments in my superclass concerning dangers and performance issues

copyright
COPYRIGHT (c) 2016 by eXept Software AG
             All Rights Reserved

This software is furnished under a license and may be used
only in accordance with the terms of that license and with the
inclusion of the above copyright notice.   This software may not
be provided or otherwise made available to, or used by, any
other person.  No title to or ownership of the software is
hereby transferred.

Instance protocol:

 add: aLinkOrAnyOtherObject

adds aLink to the end of the sequence. Returns aLink

Usage example(s):

|l e1 e2| l := DoubleLinkedList new. e1 := l add:'one'. e2 := l add:'two'. self assert:(l firstLink == e1). self assert:(l lastLink == e2). self assert:(e1 nextLink == e2). self assert:(e2 nextLink isNil). self assert:(e1 previousLink isNil). self assert:(e2 previousLink == e1).

 add: aLinkOrAnyOtherObject after: aLinkOrValue

|l e1 e2 e3 e2_5 e4|
l := DoubleLinkedList new.
e1 := l add:'one'.
e2 := l add:'two'.
e3 := l add:'three'.
self assert:(l firstLink == e1).
self assert:(e1 nextLink == e2).
self assert:(e2 nextLink == e3).
self assert:(e3 nextLink isNil).

self assert:(l lastLink == e3).
self assert:(e3 previousLink == e2).
self assert:(e2 previousLink == e1).
self assert:(e1 previousLink isNil).

e2_5 := l add:'twoPointFife' after:e2.
self assert:(l firstLink == e1).
self assert:(e1 nextLink == e2).
self assert:(e2 nextLink == e2_5).
self assert:(e2_5 nextLink == e3).
self assert:(e3 nextLink isNil).

self assert:(l lastLink == e3).
self assert:(e3 previousLink == e2_5).
self assert:(e2_5 previousLink == e2).
self assert:(e2 previousLink == e1).
self assert:(e1 previousLink isNil).

e4 := l add:'four' after:e3.
self assert:(l firstLink == e1).
self assert:(e1 nextLink == e2).
self assert:(e2 nextLink == e2_5).
self assert:(e2_5 nextLink == e3).
self assert:(e3 nextLink == e4).
self assert:(e4 nextLink isNil).

self assert:(l lastLink == e4).
self assert:(e4 previousLink == e3).
self assert:(e3 previousLink == e2_5).
self assert:(e2_5 previousLink == e2).
self assert:(e2 previousLink == e1).
self assert:(e1 previousLink isNil).

 addFirst: aLinkOrAnyOtherObject

adds aLink to the beginning of the sequence. Returns aLink

Usage example(s):

|l e1 e0| l := DoubleLinkedList new. e1 := l add:'one'. e0 := l addFirst:'zero'. self assert:(l firstLink == e0). self assert:(l lastLink == e1). self assert:(e0 nextLink == e1). self assert:(e1 nextLink isNil). self assert:(e0 previousLink isNil). self assert:(e1 previousLink == e0).

 remove: aLinkOrValue ifAbsent: exceptionBlock

remove the argument, aLinkOrValue from the sequence and return it;
if absent, evaluate the exceptionBlock.

Usage example(s):

|l e1 e2 e3 e2_5 e4| l := DoubleLinkedList new. e1 := l add:'one'. e2 := l add:'two'. e3 := l add:'three'. self assert:(l firstLink == e1). self assert:(e1 nextLink == e2). self assert:(e2 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e2). self assert:(e2 previousLink == e1). self assert:(e1 previousLink isNil). l remove:'two'. self assert:(l firstLink == e1). self assert:(e1 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e1). self assert:(e1 previousLink isNil). l remove:'one'. self assert:(l firstLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink isNil). l remove:'three'. self assert:(l size == 0).

 removeFirst

remove and return the first node from the sequence

Usage example(s):

|l v1 v2 v3 e1 e2 e3 e2_5 e4| l := DoubleLinkedList new. e1 := l add:'one'. e2 := l add:'two'. e3 := l add:'three'. self assert:(l firstLink == e1). self assert:(e1 nextLink == e2). self assert:(e2 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e2). self assert:(e2 previousLink == e1). self assert:(e1 previousLink isNil). l removeFirst. self assert:(l firstLink == e2). self assert:(e2 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e2). self assert:(e2 previousLink isNil). l removeFirst. self assert:(l firstLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink isNil). l removeFirst. self assert:(l size == 0).

 removeIdentical: aLinkOrValue ifAbsent: exceptionBlock

remove the argument, aLinkOrValue from the sequence and return it;
if absent, evaluate the exceptionBlock.

Usage example(s):

|l v1 v2 v3 e1 e2 e3 e2_5 e4| l := DoubleLinkedList new. e1 := l add:(v1 := 'one'). e2 := l add:(v2 := 'two'). e3 := l add:(v3 := 'three'). self assert:(l firstLink == e1). self assert:(e1 nextLink == e2). self assert:(e2 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e2). self assert:(e2 previousLink == e1). self assert:(e1 previousLink isNil). l removeIdentical:v2. self assert:(l firstLink == e1). self assert:(e1 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e1). self assert:(e1 previousLink isNil). l removeIdentical:v1. self assert:(l firstLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink isNil). l removeIdentical:v3. self assert:(l size == 0).

 removeLast

remove and return the last node from the sequence

Usage example(s):

|l v1 v2 v3 e1 e2 e3 e2_5 e4| l := DoubleLinkedList new. e1 := l add:'one'. e2 := l add:'two'. e3 := l add:'three'. self assert:(l firstLink == e1). self assert:(e1 nextLink == e2). self assert:(e2 nextLink == e3). self assert:(e3 nextLink isNil). self assert:(l lastLink == e3). self assert:(e3 previousLink == e2). self assert:(e2 previousLink == e1). self assert:(e1 previousLink isNil). l removeLast. self assert:(l firstLink == e1). self assert:(e1 nextLink == e2). self assert:(e2 nextLink isNil). self assert:(l lastLink == e2). self assert:(e2 previousLink == e1). self assert:(e1 previousLink isNil). l removeLast. self assert:(l firstLink == e1). self assert:(e1 nextLink isNil). self assert:(l lastLink == e1). self assert:(e1 previousLink isNil). l removeLast. self assert:(l size == 0).

 removeLink: link

Remove the specified link.
When link is not part of me, the result is undefined.
Return the removed internal link.

Examples:

    |l|

    l := DoubleLinkedList new.
    l addLast:'one'.
    l addLast:'two'.
    l addLast:'three'.
    l addLast:'four'.
    l inspect

    |l|

    l := LinkedList new.
    l addLast:(ValueDoubleLink new value:'one').
    l addLast:(ValueDoubleLink new value:'two').
    l addLast:(ValueDoubleLink new value:'three').
    l addLast:(ValueDoubleLink new value:'four').
    (l at:3) value inspect.        'slow operation for large lists'.

    |l link|

    l := LinkedList new.
    l addLast:(ValueDoubleLink new value:'one').
    l addLast:(ValueDoubleLink new value:'two').
    l addLast:(ValueDoubleLink new value:'three').
    l addLast:(ValueDoubleLink new value:'four').
    link := l removeFirst.
    l addLast:link.
    l inspect.