Linked lists · القوائم المرتبطة (Linked lists)
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
العقد المتصلة بالمؤشرات
- القائمة المرتبطة هي سلسلة من الهياكل الصغيرة تسمى العقد، مبعثرة في الرصيف (heap).
- كل عقدة تحمل قيمة ومؤشراً إلى العقدة التالية. اتبع المؤشرات لتتجول في القائمة.
- على عكس المصفوفة، يمكن للقائمة أن تنمو بعقدة واحدة في كل مرة دون تحريك البقية.
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
هيكل ذاتي الإرجاع
- العقدة هي هيكل يحتوي على مؤشر إلى نوعها الخاص:
struct Node { int data; struct Node *next; };—dataهي القيمة،nextيشير إلى العقدة التالية.- هذا معطى لك كـ
Nodeفي كل ملف بدء.nextالعقدة الأخيرة هوNULL.
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
الرأس والنهاية NULL
- مؤشر واحد، الـ رأس، يشير إلى العقدة الأولى. منه تصل إلى الباقي.
- آخر عقدة تشير إلى
NULL، الذي يمثل نهاية القائمة. - القائمة الفارغة هي ببساطة
head == NULL— لا توجد عقد على الإطلاق.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
إضافة عقدة في البداية
- للإضافة في البداية، اصنع عقدة جديدة، وجه
nextالخاص بها نحو الرأس القديم، وأرجع العقدة الجديدة كرأس جديد. - هذا سريع — لا يلمس أي عقدة أخرى.
- بما أن الرأس يتغير، فإن الدالة ترجع الرأس الجديد، والمُدْعِي يحفظه.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
أخطاء شائعة
- لا تفقد مؤشر
headأبداً، أو ستصبح القائمة بأكملها غير قابلة للوصول. - قم بإفراغ كل عقدة؛ العقدة الأخيرة تشير إلى
NULL.
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
الآن جرب بنفسك
- تجول في قائمة باستخدام مؤشر
curوcur = cur->next، متوقفاً عندNULL. - العقد الجديدة تأتي من
malloc(sizeof(Node))؛ الكاشف يحرر القائمة. لا اكتبmain.
Nodes and pointers · العقد والمؤشرات
Each node points to the next; insert/delete by re-linking. · كل عقدة تشير إلى التالية؛ الإدراج/الحذف يتم عن طريق إعادة الربط.
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not write a main. · أكمل int length(const Node *head) لعد العقد في القائمة (0 للقائمة الفارغة). تحرك مع ->next حتى NULL. نوع الـ Node مُعطى. لا تكتب a main.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not write a main. · أكمل int sum_list(const Node *head) لإرجاع مجموع كل data لكل عقدة (0 للقائمة الفارغة). نوع الـ Node مُعطى. لا تكتب a main.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not write a main. · أكمل Node *push_front(Node *head, int value) لإنشاء عقدة جديدة (مع malloc)، وتوجيه next منها نحو الـ head القديم، وإرجاعها كرأس جديد. المتحقق يحرر القائمة. لا تكتب a main.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.