Singly-linked list/Element definition: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 138: / Line 138: @@
 =={{header|Forth}}==
+Idiomatically,
-Forth has no "struct" facility, but you can easily implement a single linked list with a data cell using a double-cell value.
-<lang forth>: >cell-link ( a -- a )  ;
+<lang forth>0 value numbers
-: >cell-data ( a -- b )  cell+ ;</lang>
+: push ( n -- )
+  here swap numbers , , to numbers ;</lang>
+NUMBERS is the head of the list, initially nil (= 0); PUSH adds an element to the list; list cells have the structure {Link,Number}.  Speaking generally, Number can be anything and list cells can be as long as desired (e.g., {Link,N1,N2} or {Link,Count,"a very long string"}), but the link is always first - or rather, a link always points to the next link, so that NEXT-LIST-CELL is simply fetch (@).  Some operations:
-As an example of usage, here is a word to link 'a' after 'b'
-<lang forth>: chain ( a b -- )  \ links 'a' after 'b'
+<lang forth>: length ( list -- u )
+swap begin dup while 1 under+ @ repeat drop ;
-   over >r
-   dup >cell-link @  r> >cell-link !   \ a points at b's old link
-   >cell-link ! ;</lang>
+: head ( list -- x )
-Or with named parameters:
+  cell+ @ ;
-<lang forth>: chain { a b -- }
+: .numbers ( list -- )
+  begin dup while dup head . @ repeat drop ;</lang>
-   b >cell-link @  a >cell-link !
-   a  b >cell-link ! ;</lang>
+Higher-order programming, simple continuations, and immediate words can pull out the parallel code of LENGTH and .NUMBERS .  Anonymous and dynamically allocated lists are as straightforward.
-Due to Forth's lack of typechecking, 'b' in the above examples does not have to be an actual cell, but can instead be the head pointer of the list.
-If you assume the links always point to each other, you can abbreviate the code to:
-<lang forth>\ insert `new` after `this`
-: insert-after ( new this -- )
-dup @ swap ( this.next new ) !  ( new this ) ! ;</lang>
-And to remove data from a list:
-<lang forth>\ remove and return the item after `this`.
-: remove-next ( this -- next )
-    dup @  ( this next )
-    dup @  ( this next next.next )
-    rot   ( next  next.next this ) ! ;</lang>
 =={{header|Fortran}}==