piątek, 7 maja 2021

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.