Συνδεδεμένες λίστες

Ορισμός

• Η συνδεδεμένη λίστα (linked list) είναι μια γραμμική διάταξη στοιχείων των οποίων η σειρά ορίζεται έμμεσα με τη βοήθεια δεικτών.
• Κάθε στοιχείο της λίστας περιέχει και έναν δείκτη (pointer) ο οποίος δείχνει τη θέση του επόμενου στοιχείου.
• Το τέλος της λίστας απεικονίζεται με έναν δείκτη που περιέχει μια ειδική τιμή καθορισμένη με σύμβαση.

Υλοποίηση στη μνήμη

• Κάθε στοιχείο περιέχει εκτός από τα δεδομένα του και ένα δείκτη.
• Τα στοιχεία φυλάσσονται σε τυχαίες θέσεις.
• Ο δείκτης κάθε στοιχείου δείχνει τη διεύθυνση του επόμενου στοιχείου.
• Ένας δείκτης με ειδική τιμή (καθορισμένη με σύμβαση π.χ. 0) δείχνει ότι το τελευταίο στοιχείο δεν ακολουθείται από άλλο.
• Η διαχείριση της μνήμης γίνεται συνήθως από ειδικό υποσύστημα τον κατανεμητή μνήμης (memory allocator).
• Σε περιπτώσεις όπου η μνήμη δεν ελευθερώνεται μέσω του κατανεμητή ένα άλλο υποσύστημα φροντίζει για την αποκομιδή αχρήστων (garbage collection).

Υλοποίηση με πίνακα

• Η συνδεδεμένη λίστα υλοποιείται με βάση δύο πίνακες με ίδιο μήκος.
• Ο ένας πίνακας περιέχει τα στοιχεία και ο δεύτερος περιέχει την επόμενη θέση για κάθε στοιχείο.
• Οι άδειες θέσεις του πίνακα μπορούν να παριστάνονται με μια ειδική τιμή αντί για δείκτη ή με τη χρήση μιας άλλης συνδεδεμένης λίστας.

Υλοποίηση σε Pascal

• Οι δείκτες υλοποιούνται με τη χρήση δεικτών της Pascal.
• Τα στοιχεία ομαδοποιούνται με τους δείκτες ως μια εγγραφή.
• Το τέλος της λίστας συμβολίζεται με την ειδική τιμή δείκτη της Pascal nil.
• Μνήμη για κάθε στοιχείο αποκτούμε με τη χρήση της διαδικασίας new.

program list;

type
    intList = ^intListElem;

    intListElem = record
        val : integer;
        next : intList;
    end;


var
    theList, node : intList;

begin
    new(node);
    node^.val := 5;
    node^.next := nil;
    theList := node;

    new(node);
    node^.val := 12;
    node^.next := theList;
    theList := node
end.

Αφηρημένος τύπος

{ Ορισμός του τύπου της συνδεδεμένης λίστας }

type
    intList = ^intListElem;

    intListElem = record
        val : integer;
        next : intList;
    end;

{ Επιστρέφεται μια άδεια συνδεδεμένη λίστα }

function newIntList : intList;

{ Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i στην αρχή της }

function addIntList(l : intList; i : integer) : intList;

{ Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο i διαγραμμένο }

function delIntList(l : intList; i : integer) : intList;

{ Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή i }

function searchIntList(l : intList; i : integer) : intList;

{ Επιστρέφεται αληθές αν η λίστα είναι κενή }

function isEmtyIntList(l : intList) : boolean;

Ειδικές μορφές λιστών

διπλά συνδεδεμένη λίστα (doubly linked list)

Κάθε στοιχείο της λίστας έχει δείκτες στο προηγούμενο και το επόμενο.

κυκλικά συνδεδεμένη λίστα

Το τελευταίο στοιχείο της λίστας δείχνει ξανά το πρώτο. Η δομή αυτή ονομάζεται και δακτύλιος (ring).

κυκλικά διπλά συνδεδεμένη λίστα

Σύνθεση των παραπάνω.

Εφαρμογές

• Υλοποίηση δομών δεδομένων με δυναμικά αυξανόμενο μέγεθος.
• Διαχείριση μνήμης.
• Οργάνωση δεδομένων σε πολλαπλές δομές.

Βιβλιογραφία

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 63-80 Εκδόσεις Νέων Τεχνολογιών, 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms, pages 37–52. Addison-Wesley, 1983.
• Hans-Juergen Boehm. Garbage collection in an uncooperative environment. Software: Practice & Experience, 18(9):807–820, September 1988.
• Jacques Cohen. Garbage collection of linked data structures. Computing Surveys, 13(3):339–367, September 1981.
• Donald E. Knuth. The Art of Computer Programming, volume 1 / Fundamental Algorithms, pages 251–258. Addison-Wesley, second edition, 1973.
• Robert Sedgewick. Algorithms in C, pages 17–22. Addison-Wesley, 1990.
• Norihisa Suzuki. Analysis of pointer ``rotation''. Communications of the ACM, 25(5):330–335, May 1982.
• Niklaus Wirth. Algorithms and Data Structures, pages 180–182. Prentice–Hall, 1986.

Ασκήσεις

Άσκηση ADS04

1. Να υλοποιηθεί σε Pascal ο αφηρημένος τύπος της συνδεδεμένης λίστας χαρακτήρων σύμφωνα με τις παρακάτω συναρτήσεις:

   { Ορισμός του τύπου της συνδεδεμένης λίστας }

   type
       charList = ...
   

   { Επιστρέφεται μια άδεια συνδεδεμένη λίστα }

   function newCharList : charList;

   { Επιστρέφεται μια συνδεδεμένη λίστα με το στοιχείο c στην αρχή της }

   function addCharList(l : charList; c : char) : charList;

   { Επιστρέφεται μια συνδεδεμένη λίστα με το πρώτο στοιχείο διαγραμμένο. Κατά την επιστροφή η μεταβλητή c περιέχει την τιμή του. }

   function delCharListHead(l : charList; var c : char) : charList;

   { Επιστρέφεται ένας δείκτης στο στοιχείο της λίστας που έχει την τιμή c }

   function searchCharList(l : charList; c : char) : charList;

   { Επιστρέφεται αληθές αν η λίστα είναι κενή }

   function isEmtyCharList(l : charList) : boolean;

2. Με βάση τον αφηρημένο αυτό τύπο να υλοποιηθεί πρόγραμμα το οποίο να διαβάζει μια σειρά χαρακτήρων μέχρι να συναντήσει μια τελεία και στη συνέχεια να τυπώνει τους χαρακτήρες αυτούς με την αντίστροφη σειρά.
   Παράδειγμα:

   L
   I
   V
   E
   .
   E
   V
   I
   L
   

   Περισσότερες λεπτομέρειες για τις ασκήσεις
   • Περιεχόμενα

    Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:30 μμ
    Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».