یک لیست پیوندی یک ساختار داده است که از دنباله ای از گره ها تشکیل شده است، جایی که هر گره حاوی یک مقدار و یک اشاره گر به گره بعدی در لیست است. در C، می توانید با تعریف ساختاری که نشان دهنده یک گره و حاوی فیلدهای لازم است، یک لیست پیوندی ایجاد کنید. در اینجا مثالی از نحوه ایجاد یک لیست پیوندی از اعداد صحیح آورده شده است:
struct Node {
int data;
struct Node* next;
};
این ساختار گره ای را تعریف می کند که حاوی یک مقدار صحیح (داده) و یک اشاره گر به گره بعدی در لیست (بعدی) است.
برای ایجاد یک گره جدید، می توانید از تابع malloc() برای تخصیص حافظه برای یک گره جدید استفاده کنید و سپس از عملگر -> برای تنظیم داده ها و فیلدهای بعدی استفاده کنید:
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
برای افزودن یک گره جدید به لیست، می توانید یک گره جدید ایجاد کنید و نشانگر بعدی آخرین گره فعلی را طوری تنظیم کنید که به گره جدید اشاره کند. برای انجام این کار، باید یک ارجاع به سر لیست، که اولین گره در لیست است، و یک ارجاع به انتهای لیست، که آخرین گره در لیست است، حفظ کنید. در اینجا مثالی از نحوه اضافه کردن یک گره جدید به لیست آورده شده است:
void push(struct Node** head_ref, int new_data) {
/* allocate node */
struct Node* new_node = newNode(new_data);
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
حذف یک گره از یک لیست پیوندی در C مستلزم به روز رسانی اشاره گر گره های قبلی و بعدی برای دور زدن گره ای است که حذف می شود. در اینجا مثالی از نحوه حذف یک گره از یک لیست پیوندی آورده شده است:
void removeNode(struct Node** head_ref, int key) {
/* Store head node */
struct Node* temp = *head_ref, *prev;
/* If head node itself holds the key to be deleted */
if (temp != NULL && temp->data == key) {
*head_ref = temp->next; // Changed head
free(temp); // free old head
return;
}
/* Search for the key to be deleted, keep track of the
previous node as we need to change 'prev->next' */
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
/* If key was not present in linked list */
if (temp == NULL) return;
/* Unlink the node from linked list */
prev->next = temp->next;
free(temp); // Free memory
}
در مثال بالا، ابتدا بررسی می‌کنیم که آیا هد نود کلیدی را که می‌خواهیم حذف کنیم نگه می‌دارد یا خیر، در این صورت مرجع هد را به‌روزرسانی می‌کنیم و حافظه هد قدیمی را آزاد می‌کنیم.
اگر کلید در هد نباشد، با پیگیری گره قبلی، لیست را طی می کنیم تا زمانی که گره را با کلید پیدا کنیم. هنگامی که گره را پیدا کردیم، اشاره گر بعدی گره قبلی را به روز می کنیم تا به گره بعدی اشاره کند، گرهی را که می خواهیم حذف کنیم را دور می زنیم و سپس حافظه گره حذف شده را آزاد می کنیم.
مهم است که توجه داشته باشید که حذف یک گره می تواند کمی مشکل باشد، بررسی موارد لبه بسیار مهم است، مانند اینکه آیا لیست خالی است یا اگر کلید در لیست نیست.