Singly-linked list/Element insertion

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;
}

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()
}