Singly-linked list/Element insertion
You are encouraged to solve this task according to the task description, using any language you may know.
Using the link element defined in Singly-Linked List (element), define a method to insert an element into a singly-linked list following a given element.
Using this method, insert an element C into a list comprised of elements A->B, following element A.
Ada
We must create a context clause making the pre-defined generic procedure Ada.Unchecked_Deallocation visible to this program.
with Ada.Unchecked_Deallocation; -- Define the link type procedure Singly_Linked is type Link; type Link_Access is access Link; type Link is record Data : Integer; Next : Link_Access := null; end record; -- Instantiate the generic deallocator for the link type procedure Free is new Ada.Unchecked_Deallocation(Link, Link_Access); -- Define the procedure procedure Insert_Append(Anchor : Link_Access; Newbie : Link_Access) is begin if Anchor /= null and Newbie /= null then Newbie.Next := Anchor.Next; Anchor.Next := Newbie; end if; end Insert_Append; -- Create the link elements A : Link_Access := new Link'(1, null); B : Link_Access := new Link'(2, null); C : Link_Access := new Link'(3, null); -- Execute the program begin Insert_Append(A, B); Insert_Append(A, C); Free(A); Free(B); Free(C); end Singly_Linked;
C
Define the method:
void insert_append (link *anchor, link *newlink) { newbie->next = anchor->next; anchor->next = newlink; }
Note that in a production implementation, one should check anchor and newlink to ensure they're valid values. (I.e., not NULL.)
And now on to the code.
Create our links.
link *a, *b, *c; a = malloc(sizeof(link)); b = malloc(sizeof(link)); c = malloc(sizeof(link)); a->data = 1; b->data = 2; c->data = 3;
Prepare our initial list
insert_append (a, b);
Insert element c after element a
insert_append (a, c);
Remember to free the memory once we're done.
free (a); free (b); free (c);
C++
This uses the generic version of the link node. Of course, normally this would be just some implementation detail inside some list class, not to be used directly by client code.
template<typename T> void insert_after(link<T>* list_node, link<T>* new_node) { new_node->next = list_node->next; list_node->next = new_node; };
Here's the example code using that method:
The following code creates the links. As numeric values I've just taken the corresponding character values.
link<int>* a = new link<int>('A', new link<int>('B')); link<int>* c = new link<int>('C');
Now insert c after a:
insert_after(a, c);
Finally destroy the list:
while (a) { link<int>* tmp = a; a = a->next; delete tmp; }
Forth
Using the linked list concept described in the Singly-Linked_List_(element) topic:
\ Create the list and some list elements create A 0 , char A , create B 0 , char B , create C 0 , char C ,
Now insert b after a and c after b, giving a->b->c
B A chain C B chain
Here is an abbreviated version of the definition of 'chain' from the other article:
: chain ( a b -- ) 2dup @ swap ! ! ;
And here is a function to walk a list, calling an XT on each data cell:
: walk ( a xt -- ) >r begin ?dup while dup cell+ @ r@ execute @ repeat r> drop ;
Testing code:
A ' emit walk ABC ok
[Delphi / Object Pascal / >>Turbo Pascal / Standard Pascal<<]
A simple insertion into a one way list. I use a generic pointer for the data that way it can point to any structure, individual variable or whatever. NOTE: For original versions of Turbo Pascal and Standard Pascal, substitute the MemAvail Function for the Try Except block as this does not exist in these versions of the pascal language.
// Using the same type defs from the one way list example. Type // The pointer to the list structure pOneWayList = ^OneWayList; // The list structure OneWayList = record pData : pointer ; Next : pOneWayList ; end; // I will illistrate a simple function that will return a pointer to the // new node or it will return NIL. In this example I will always insert // right, to keep the code clear. Since I am using a function all operations // for the new node will be conducted on the functions result. This seems // somewaht counter intuitive, but it is the simplest way to accomplish this. Function InsertNode(VAR CurrentNode:pOneWayList): pOneWayList begin // I try not to introduce different parts of the language, and keep each // example to just the code required. in this case it is important to use // a try/excpet block. In any OS that is multi-threaded and has many apps // running at the same time, you cannot rely on a call to check memory available // and then attempting to allocate. In the time between the two, another // program may have grabbed the memory you were trying to get. Try // Try to allocate enough memory for a veriable the size of OneWayList GetMem(Result,SizeOf(OneWayList)); Except On EOutOfMemoryError do begin Result := NIL exit; end; end; // Initialize the variable. Result.Next := NIL ; Reuslt.pdata := NIL ; // Ok now we will insert to the right. // Is the Next pointer of CurrentNode Nil? If it is we are just tacking // on to the end of the list. if CurrentNode.Next = NIL then CurrentNode.Next := Result else // We are inserting into the middle of this list Begin Result.Next := CurrentNode.Next ; CurrentNode.Next := result ; end; end;
E
def insertAfter(head :LinkedList ? (!head.null()), new :LinkedList ? (new.next().null())) { new.setNext(head.next()) head.setNext(new) }
def a := makeLink(1, empty) def b := makeLink(2, empty) def c := makeLink(3, empty) insertAfter(a, b) insertAfter(a, c)
var x := a while (!x.null()) { println(x.value()) x := x.next() }
Haskell
This kind of list manipulation is unidiomatic Haskell. But you can try the following:
insertAfter a b (c:cs) | a==c = a : b : cs | otherwise = c : insertAfter a b cs insertAfter _ _ [] = error "Can't insert"
Perl
Just use an array. You can traverse and splice it any way. Linked lists are way too low level.
my @l = ($A, $B); push @l, $C, splice @l, 1;
However, if all you got is an algorithm in a foreign language, you can use references to accomplish the translation.
my %A = ( data => 1, next => \%B, ); my %B = ( data => 3, next => undef, # not a circular list ); my %C = ( data => 2, ); $C{next} = \%B; $A{next} = \%C;
Pop11
In Pop11 one normally uses builtion lists:
define insert_into_list(anchor, x); cons(x, back(anchor)) -> back(anchor); enddefine; ;;; Build inital list lvars l1 = cons("a", []); insert_into_list(l1, "b"); ;;; insert c insert_into_list(l1, "c");
If one wants one can use user-defined list node (for convenience we repeat definition of list node):
uses objectclass; define :class ListNode; slot value = []; slot next = []; enddefine;
define insert_into_List(anchor, x); consListNode(x, next(anchor)) -> next(anchor); enddefine; ;;; Build inital list lvars l2 = consListNode("a", []); insert_into_List(l2, "b"); ;;; insert c insert_into_List(l2, "c");
Note that user-defined case differs from builtin case only because of names.
Ruby
class ListNode def insertAfter(a,b) if a==value self.succ = ListNode.new(b,succ) else succ.insertAfter(a,b) end end end
list = ListNode.new(:a,ListNode.new(:b)) list.insertAfter(:a,:c)