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

Ορισμός

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

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

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

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

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

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

• Οι δείκτες υλοποιούνται με τη χρήση δεικτών της C.
• Τα στοιχεία ομαδοποιούνται με τους δείκτες ως μια εγγραφή:

  /* List of integers */
  struct s_list {
  	int val;		/* Integer value */
  	struct s_list *next;
  };
  

• Το τέλος της λίστας συμβολίζεται με την ειδική τιμή δείκτη της C NULL.
• Μνήμη για κάθε στοιχείο αποκτούμε με τη χρήση της διαδικασίας malloc.
• Αν ο δείκτης head δείχνει την αρχή μιας λίστας μπορούμε να προσθέσουμε ένα στοιχείο στη λίστα με τον παρακάτω κώδικα:

  	struct s_list *head, *p;
  
  	p = (struct s_list *)malloc(sizeof(struct s_list));
  	p->next = head;
  	/* Set other members of p */
  	head = p;
  

• Για να διασχίσουμε μια λίστα ο παρακάτω κώδικας είναι τυπικός:

  	for (p = head; p; p = p->next)
  		/* Process element p */
  

• Για να διαγράψουμε τα στοιχεία μιας λίστας πρέπει να προσέξουμε να μη χρησιμοποιήσουμε δεδομένα από στοιχεία που έχουμε ελευθερώσει.
  Λάθος:

  	free(p);
  	p = p->next;
  

  Σωστό:

  	tmp = p->next;
  	free(p);
  	p = tmp;
  

#include <stdlib.h>
#include <stdio.h>

/* List of integers */
struct s_list {
	int val;		/* Integer value */
	struct s_list *next;
};

main()
{
	struct s_list *head, *p;
	int n;

	head = NULL;
	/* Read list elements */
	while (scanf("%d", &n) == 1) {
		p = (struct s_list *)malloc(sizeof(struct s_list));
		p->val = n;
		p->next = head;
		head = p;
	}

	printf("\nStarting output:\n");
	/* Print list elements */
	for (p = head; p; p = p->next)
		printf("%d\n", p->val);
}

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

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

typedef struct s_int_list *int_list;

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

int_list list_new(void);

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

int_list int_list_add(int_list l, int i);

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

int_list int_list_del(int_list l, int i);

Επιστρέφει αληθές αν κάποιο στοιχείο της λίστας έχει την τιμή i, αλλιώς ψευδές.

int int_list_search(int_list l, int i);

Καλεί τη συνάρτηση process για κάθε στοιχείο της λίστας

void int_list_traverse(int_list l, void (*process)(int i));

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

int int_list_isempty(int_list l);

Διαγράφει όλα τα στοιχεία της λίστας l

void int_list_delete(int_list l);

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

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

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

struct s_int_dlist {
	int	val;			/* Integer value */
	struct s_int_dlist *prev;	/* Previous element */
	struct s_int_dlist *next;	/* Next element */
};

Η εισαγωγή ενός στοιχείου np πριν από το στοιχείο της λίστας p γίνεται με τις παρακάτω εντολές:

	p->prev->next = np;
	np->next = p;
	np->prev = p->prev;
	p->prev = np;

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

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

	struct s_dlist *start, *p;

	p = start;
	if (p)
		do {
			/* Process list element */
			...
			p = p->next;
		} while (p != start);

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

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

Εφαρμογές

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

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

• Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 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.

Ασκήσεις

Άσκηση 3

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

   Ορισμός του τύπου της συνδεδεμένης λίστας χαρακτήρων

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

   char_list char_list_new(void);

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

   char_list char_list_add(char_list l, char c);

   Καλεί τη συνάρτηση process για κάθε στοιχείο της λίστας

   void char_list_traverse(char_list l, void (*process)(char c));

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

   int char_list_isempty(char_list l);

   Διαγράφει όλα τα στοιχεία της λίστας l

   void char_list_delete(char_list l);

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

   L
   I
   V
   E
   .
   E
   V
   I
   L
   

   • Περιεχόμενα

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