C - Linked list - Jednokierunkowa

W tym poście chciałbym opisać sposób wykonania listy powiązanej (ang. Linked list) w C. 

Linked list jest to liniowa struktura danych nieposiadająca zdeklarowanej długości. Opiszę przykładowe rozwiązanie jednokierunkowe, czyli każdy element będzie zawierał wskaźnik na następny element z listy.

Funkcje obsługujące będą wykonywać następujące operacje:

- Dodanie elementu do listy;

- Usunięcie elementu z listy;

- Usunięcie elementu o podanej wartości,

- Usunięcie elementu z podanej pozycji,

- Znalezienie elementu na liście,

- Sprawdzenie czy lista jest pusta,

- Obliczenie wielkości listy,

- Odwrócenie elementów lisy.

Struktura przechowująca dane wygląda następująco:

1. struct LinkedListData_s {
2.     uint8_t data;
3.     struct LinkedListData_s* nextEl;
4. };

W liście można umieszczać każdy rodzaj danych jaki jest potrzebny. Jedynym niezmiennym elementem jest wskaźnik na kolejny element w tablicy. Bez niego, lub gdy zostanie on przypadkowo usunięty, lista będzie bezużyteczna, ponieważ nie uda się odnaleźć kolejnej wartości.

Dodanie elementu na początek listy:

1. void ll_insert_first_element(struct LinkedListData_s * headData, struct LinkedListData_s ** headPtr, uint8_t data) {
2.    struct LinkedListData_s *lldata = (struct LinkedListData_s*)malloc(sizeof(struct LinkedListData_s));
3.    lldata->data = data;
4.    lldata->nextEl = headData;
5.    *headPtr = lldata;
6. }

Usunięcie elementu z początku listy:

1. struct LinkedListData_s* ll_delete_first_element(struct LinkedListData_s *headPtr) {
2.    struct LinkedListData_s *tempPtr = headPtr;
3.  
4.    if(headPtr == NULL) { return NULL; }
5.  
6.    head = tempPtr->nextEl;
7.    return tempPtr;
8. }

Usunięcie pierwszego elementu o podanej wartości:

1. struct LinkedListData_s* ll_delete_by_value(struct LinkedListData_s *headPtr, uint8_t value) {
2.    struct LinkedListData_s* cur = headPtr;
3.    struct LinkedListData_s* prev = NULL;
4.    
5.    if(head == NULL) { return NULL; }
6.  
7.    while(cur->data != value) {
8.       if(cur->nextEl == NULL) { return NULL; }
9.       else {
10.          prev = cur;
11.          cur = cur->nextEl;
12.       }
13.    }
14.  
15.    if(cur == headPtr) { headPtr = headPtr->nextEl; }
16.    else { prev->nextEl = cur->nextEl; }    
17.    
18.    return cur;
19. }

Usunięcie elementu o podanej pozycji:

1. struct LinkedListData_s* ll_delete_by_position(struct LinkedListData_s *headPtr, uint8_t position) {
2.    struct LinkedListData_s* cur = headPtr;
3.    struct LinkedListData_s* prev = NULL;
4.    uint16_t act_pos = 0;   
5.  
6.    if(head == NULL) { return NULL; }
7.  
8.    while(act_pos != position) {
9.       act_pos++;
10.       if(cur->nextEl == NULL) { return NULL; }
11.       else {
12.          prev = cur;
13.          cur = cur->nextEl;
14.       }
15.    }
16.  
17.    if(cur == headPtr) { headPtr = headPtr->nextEl; }
18.    else { prev->nextEl = cur->nextEl; }    
19.    
20.    return cur;
21. }

Wyświetlenie wszystkich elementów zapisanych na liście:

1. void ll_print_list(struct LinkedListData_s *headPtr) {
2.    struct LinkedListData_s *ptr = headPtr;
3.    while(ptr != NULL) {
4.       printf("((DEC) - %d; (HEX) - 0x%.2x\r\n", ptr->data, ptr->data);
5.       ptr = ptr->nextEl;
6.    }
7. }

Wyszukanie elementu na liście:

1. int32_t ll_search_value(struct LinkedListData_s *headPtr, uint8_t value) {
2.    struct LinkedListData_s *ptr = headPtr;
3.    uint16_t positionInList = 0;
4.    while(ptr != NULL) {
5.        if(ptr->data == value) {
6.            return positionInList;
7.        }
8.        positionInList++;
9.        ptr = ptr->nextEl;
10.    }
11.  
12.    return -1;
13. }

Pobranie rozmiaru:

1. uint16_t ll_get_list_size(struct LinkedListData_s *headPtr) {
2.     struct LinkedListData_s *ptr = headPtr;
3.     uint16_t list_len = 0;
4.  
5.     while(ptr != NULL) {
6.        list_len++;
7.        ptr = ptr->nextEl;
8.    }
9.  
10.     return list_len;
11. }

Odwrócenie listy:

1. void ll_reverse_data(struct LinkedListData_s** headPtr) {
2.    struct LinkedListData_s* current = *headPtr;
3.    struct LinkedListData_s* prev = NULL;
4.    struct LinkedListData_s* next = NULL;
5.    
6.    while (current != NULL) {
7.       next = current->nextEl;
8.       current->nextEl = prev;  
9.       prev = current;
10.       current = next;
11.    }
12.    
13.    *headPtr = prev;
14. }

Przykładowy plik z opisanymi funkcjami można pobrać z dysku Google pod tym linkiem.