Doubly-linked list/Element insertion: Difference between revisions
(Created task definition, gave C code) |
|||
Line 3: | Line 3: | ||
This is much like inserting into a [[Singly-Linked List (element insertion)|Singly-Linked List]], but with added assignments so that the backwards-pointing links remain correct. |
This is much like inserting into a [[Singly-Linked List (element insertion)|Singly-Linked List]], but with added assignments so that the backwards-pointing links remain correct. |
||
==[[Ada]]== |
|||
[[Category:Ada]] |
|||
Define the procedure: |
|||
procedure Insert (Anchor : Link_Access; New_Link : Link_Access) is |
|||
begin |
|||
if Anchor /= Null and New_Link /= Null then |
|||
New_Link.Next := Anchor.Next; |
|||
New_Link.Prev := Anchor; |
|||
if New_Link.Next /= Null then |
|||
New_Link.Next.Prev := New_Link; |
|||
end if; |
|||
Anchor.Next := New_Link; |
|||
end if; |
|||
end Insert; |
|||
Create links and form the list. |
|||
procedure Make_List is |
|||
Link_Access : A, B, C; |
|||
begin |
|||
A := new Link; |
|||
B := new Link; |
|||
C := new Link; |
|||
A.Data := 1; |
|||
B.Data := 2; |
|||
C.Data := 2; |
|||
Insert(Anchor => A, New_Link => B); -- The list is (A, B) |
|||
Insert(Anchor => B, New_Link => C); -- The list is (A, B, C) |
|||
end Make_List; |
|||
==[[C]]== |
==[[C]]== |
Revision as of 23:52, 6 July 2007
Use the link structure defined in Doubly-Linked List (element) to define a procedure for inserting a link into a doubly-linked list. Call this procedure to insert element C into a list {A,B}, between elements A and B.
This is much like inserting into a Singly-Linked List, but with added assignments so that the backwards-pointing links remain correct.
Ada
Define the procedure:
procedure Insert (Anchor : Link_Access; New_Link : Link_Access) is begin if Anchor /= Null and New_Link /= Null then New_Link.Next := Anchor.Next; New_Link.Prev := Anchor; if New_Link.Next /= Null then New_Link.Next.Prev := New_Link; end if; Anchor.Next := New_Link; end if; end Insert;
Create links and form the list.
procedure Make_List is Link_Access : A, B, C; begin A := new Link; B := new Link; C := new Link; A.Data := 1; B.Data := 2; C.Data := 2; Insert(Anchor => A, New_Link => B); -- The list is (A, B) Insert(Anchor => B, New_Link => C); -- The list is (A, B, C) end Make_List;
C
Define the function:
void insert(link* anchor, link* newlink) { newlink->next = anchor->next; newlink->prev = anchor; (newlink->next)->prev = newlink; anchor->next = newlink; }
Production code should also include checks that the passed links are valid (e.g. not null pointers). There should also be code to handle special cases, such as when *anchor is the end of the existing list (i.e. anchor->next is a null pointer).
To call the function:
Create links, and form the list:
link a, b, c; a.next = &b; a.prev = null; a.data = 1; b.next = null; b.prev = &a; b.data = 3; c.data = 2;
This list is now {a,b}, and c is separate.
Now call the function:
insert(&a, &c);
This function call changes the list from {a,b} to {a,b,c}.