CS 131 LECTURE 9 - LINKED LIST APPLICATIONS

Stack Package Body

PACKAGE BODY Stack_Package IS
  TYPE Nodes;
  TYPE Pointers IS ACCESS Nodes;
  TYPE Nodes IS
    RECORD
      Data: Elements;
      Previous: Pointers;
    END RECORD;
  Top: Pointers;
  FUNCTION Empty RETURN Boolean IS
  BEGIN
    RETURN Top = NULL;
  END Empty;
  PROCEDURE Push(Item: IN Elements) IS
    This: Nodes;
  BEGIN
    This.Data := Item;
    This.Previous := Top;
    Top := NEW Nodes'(This);
  EXCEPTION
    WHEN Storage_Error =>
      RAISE Full_Stack;
  END Push;
  PROCEDURE Pop(Item: OUT Elements) IS
    SEPARATE;
END Stack_Package;

Pop Procedure

WITH Unchecked_Deallocation;
SEPARATE (Stack_Package)
PROCEDURE Pop(Item: OUT Elements) IS
  Old_Top: Pointers;
  PROCEDURE Deallocate_Node IS NEW
    Unchecked_Deallocation(Nodes,Pointers);
BEGIN
  IF Top = NULL THEN
    RAISE Empty_Stack;
  ELSE
    Old_Top := Top;
    Item := Top.Data;
    Top := Top.Previous;
    Deallocate_Node(Old_Top);
  END IF;
END Pop;

Sorted List Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Keys IS PRIVATE;
  WITH FUNCTION Get_Key(Element: Elements)
    RETURN Keys;
  WITH FUNCTION ">"(Left,Right: Keys) RETURN
    Boolean IS <>;
PACKAGE Sorted_List_Package IS
  TYPE Lists IS PRIVATE;
  PROCEDURE Insert(List: IN OUT Lists;
    Element: IN Elements);
  PROCEDURE Delete(List: IN OUT Lists;
    Key: IN Keys);
  PROCEDURE Find(List: IN Lists;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean);
  Full_List,Duplicate_Key: EXCEPTION;
PRIVATE
  TYPE Tables IS ARRAY(1..100) OF Elements;
  TYPE Lists IS
    RECORD
      Count: Natural := 0;
      Table: Tables;
    END RECORD;
END Sorted_List_Package;

Sorted List Package Body

PACKAGE BODY Sorted_List_Package IS
  PROCEDURE Search(List: IN Lists;
    Key: IN Keys; Location: OUT Positive;
    Found: OUT Boolean) IS SEPARATE;
  PROCEDURE Insert(List: IN OUT Lists;
    Element: IN Elements) IS
    Key: Keys := Get_Key(Element);
    Location: Natural;
    Found: Boolean;
  BEGIN
    Search(List,Key,Location,Found);
    IF Found THEN
      RAISE Duplicate_Key;
    END IF;
    IF List.Count = Tables'Last THEN
      RAISE Full_List;
    END IF;
    List.Count := List.Count + 1;
    List.Table(Location+1..List.Count) :=
      List.Table(Location..List.Count-1);
    List.Table(Location) := Element;
  END Insert;

--Package Body Continues On Next Page

Sorted List Package Body

  PROCEDURE Delete(List: IN OUT Lists;
    Key: IN Keys) IS
    Location: Natural;
    Found: Boolean;
  BEGIN
    Search(List,Key,Location,Found);
    IF Found THEN
      List.Table(Location..List.Count-1) :=
        List.Table(Location+1..List.Count);
      List.Count := List.Count - 1;
    END IF;
  END Delete;
  PROCEDURE Find(List: IN Lists;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean) IS
    Location: Natural;
    In_List: Boolean;
  BEGIN
    Search(List,Key,Location,In_List);
    IF In_List THEN
      Element := List.Table(Location);
    END IF;
    Found := In_List;
  END Find;
END Sorted_List_Package;

Search Procedure

SEPARATE (Sorted_List_Package)
PROCEDURE Search(List: IN Lists;
  Key: IN Keys; Location: OUT Positive;
  Found: OUT Boolean) IS
  Index: Positive := 1;
BEGIN
  WHILE Index <= List.Count LOOP
    EXIT WHEN
      Get_Key(List.Table(Index)) = Key OR
      Get_Key(List.Table(Index)) > Key;
    Index := Index + 1;
  END LOOP;
  Found := Index <= List.Count AND THEN
    Get_Key(List.Table(Index)) = Key;
  Location := Index;
 END Search;

Important Points:

1. The Efficiency Of The Linear Search Procedure Is O(n), It Does Not Take Advantage Of The Sorted Order, It Will Work On Unsorted Lists As Well

2. A Binary Search Utilizes The Divide And Conquer Approach That Greatly Improves The Efficiency Of The Search, Its Efficiency Is O(log2 n )

Search Procedure

SEPARATE (Sorted_List_Package)
PROCEDURE Search(List: IN Lists;
  Key: IN Keys; Location: OUT Positive;
  Found: OUT Boolean) IS
  Lower,Mid: Positive := 1;
  Upper: Positive := List.Count;
BEGIN
  IF List.Count = 0 THEN
    Location := 1; Found := FALSE; RETURN;
  END IF;
  WHILE Lower <= Upper LOOP
    Mid := (Lower + Upper) / 2;
    EXIT WHEN Key=Get_Key(List.Table(Mid));
    IF Key > Get_Key(List.Table(Mid)) THEN
      Lower := Mid + 1;
    ELSE
      Upper := Mid - 1;
    END IF;
  END LOOP;
  Found := Get_Key(List.Table(Mid)) = Key;
  IF Key > Get_Key(List.Table(Mid)) THEN
    Location := Mid + 1;
  ELSE
    Location := Mid;
  END IF;
END Search;

Major Issues:

1. A Linked Keyed Table Can Be Built By Adding A Layer Of Abstraction On Top Of The Basic Linked List Package And Creating A Linked Sorted List

2. The Basic Linked List Package Can Be Instantiated For Any Private Type, The Linked Sorted List Requires That The Type Have A > Function Defined

3. The Linked Sorted List Package Maintains A Sorted List By Searching The List Before Insertion Or Deletion

Layer Package Diagram

Sorted List Package Specification

WITH Linked_List_Package;
GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Keys IS PRIVATE;
  WITH FUNCTION ">"(Left,Right: Keys) RETURN
    Boolean IS <>;
  WITH PROCEDURE Put(Item: Elements) IS <>;
  WITH FUNCTION Get_Key(Element: Elements)
    RETURN Keys;
PACKAGE Sorted_List_Package IS
  TYPE Lists IS PRIVATE;
  PROCEDURE Insert(List: IN OUT Lists;
    Element: IN Elements);
  PROCEDURE Delete(List: IN OUT Lists;
    Key: IN Keys);
  PROCEDURE Find(List: IN OUT Lists;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean);
  Full_List,Duplicate_Key: EXCEPTION;
PRIVATE
  PACKAGE LL IS NEW Linked_List_Package
    (Elements);
  TYPE Lists IS NEW LL.Lists;
END Sorted_List_Package;

Sorted List Package Body

PACKAGE BODY Sorted_List_Package IS
  PROCEDURE Search(List: IN Lists;
    Key: IN Keys; Last,This: IN OUT Lists;
    Found: OUT Boolean) IS
  BEGIN
    Last := NULL;
    This := List;
    WHILE This /= NULL LOOP
      EXIT WHEN Key > Get_Key(This.Data)
        OR Key = Get_Key(This.Data);;
      Last := This;
      This := Lists(This.Next);
    END LOOP;
    Found := Last /= NULL AND THEN
      Key = Get_Key(Last.Data);
  END Search;
  PROCEDURE Find(List: IN OUT Lists;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean) IS
    Last,This: Lists; In_List: Boolean;
  BEGIN
    Search(List,Key,Last,This,In_List);
    IF In_List THEN
      Element := This.Data;
    END IF;
    Found := In_List;
  END Find;

  PROCEDURE Insert(List: IN OUT Lists;
    Element: IN Elements) IS
    Key: Keys := Get_Key(Element);
    Last,This: Lists;
    Found: Boolean;
  BEGIN
    Search(List,Key,Last,This,Found);
    IF Found THEN
      RAISE Duplicate_Key;
    END IF;
    LL.Insert(LL.Lists(List),
      LL.Lists(Last), Element);
  EXCEPTION
    WHEN Storage_Error =>
      RAISE Full_List;
  END Insert;
  PROCEDURE Delete(List: IN OUT Lists;
    Key: IN Keys) IS
    Last,This: Lists;
    Found: Boolean;
  BEGIN
    Search(List,Key,Location,Found);
    IF Found THEN
      LL.Delete(LL.Lists(List),
        LL.Lists(Last));
    END IF;
  END Delete;
END Sorted_List_Package;

Sequential Representation

Advantage

1. A Binary Search Is Possible, The Efficiency Of A Binary Search Is O(log2 n)

Disadvantages

1. The Size Of The Table Must Be Fixed At Compile Time

2. The Efficiency Of Insertion And Deletion, Excluding The Search Is Linear, O(n), Because Of The Need To Move Data

Linked Representation

Advantages

1. The Size Of The Table Is Limited Only By The Memory Available In The Heap

2. Excluding The Search, The Efficiency For Insertion And Deletion Is O(1)

Disadvantage

1. The Only Possible Search Algorithm Is A Linear Search With Efficiency O(n)