Singly-linked list/Element definition: Difference between revisions
m →[[E]]: Split off Forth section |
|||
Line 85: | Line 85: | ||
==[[Forth]]== |
==[[Forth]]== |
||
[[Category:Forth]] |
[[Category:Forth]] |
||
Forth has no "struct" facility, but you can easily implement a single linked list with a data cell using a double-cell value. |
|||
: >cell-link ( a -- a ) ; |
|||
: >cell-data ( a -- b ) cell+ ; |
|||
As an example of usage, here is a word to link 'a' after 'b' |
|||
: chain ( a b -- ) \ links 'a' after 'b' |
|||
over >r |
|||
dup >cell-link @ r> >cell-link ! \ a points at b's old link |
|||
>cell-link ! ; |
|||
Or with named parameters: |
|||
: chain { a b -- } |
|||
b >cell-link @ a >cell-link ! |
|||
a b >cell-link ! ; |
|||
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. |
Revision as of 19:16, 12 April 2007
You are encouraged to solve this task according to the task description, using any language you may know.
Define the data structure for a singly-linked list element. Said element should contain a data member capable of holding a numeric value, and the link to the next element should be mutable.
Ada
type Link; type Link_Access is access Link; type Link is record Next : Link_Access := null; Data : Integer; end record;
C
struct link { struct link *next; int data; };
C++
The simplest C++ version looks basically like the C version:
struct link { link* next; int data; };
Initialization of links on the heap can be simplified by adding a constructor:
struct link { link* next; int data; link(int a_data, link* a_next = 0): next(a_next), data(a_data) {} };
With this constructor, new nodes can be initialized directly at allocation; e.g. the following code creates a complete list with just one statement:
link* small_primes = new link(2, new link(3, new link(5, new link(7))));
However, C++ also allows to make it generic on the data type (e.g. if you need large numbers, you might want to use a larger type than int, e.g. long on 64-bit platforms, long long on compilers that support it, or even a bigint class).
template<typename T> struct link { link* next; T data; link(int a_data, link* a_next = 0): next(a_next), data(a_data) {} };
Note that the generic version works for any type, not only integral types.
Delphi / Object Pascal / Turbo Pascal / Standard Pascal
A simple one way list. I use a generic pointer for the data that way it can point to any structure, individual variable or whatever.
Type pOneWayList = ^OneWayList; OneWayList = record pData : pointer ; Next : pOneWayList ; end;
E
interface LinkedList guards LinkedListStamp {} def empty implements LinkedListStamp { to null() { return true } } def makeLink(value :int, var next :LinkedList) { def link implements LinkedListStamp { to null() { return false } to value() { return value } to next() { return next } to setNext(new) { next := new } } return link }
Forth
Forth has no "struct" facility, but you can easily implement a single linked list with a data cell using a double-cell value.
: >cell-link ( a -- a ) ; : >cell-data ( a -- b ) cell+ ;
As an example of usage, here is a word to link 'a' after 'b'
: chain ( a b -- ) \ links 'a' after 'b' over >r dup >cell-link @ r> >cell-link ! \ a points at b's old link >cell-link ! ;
Or with named parameters:
: chain { a b -- } b >cell-link @ a >cell-link ! a b >cell-link ! ;
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.