هياكل البيانات الخطية
في هذه الصفحة 8 موضوعات
نص الدروس والتمارين باللغة الإنجليزية، بينما تبقى واجهة الموقع وعناوين الدروس بالعربية.
نظرة عامة
الموضوعات
- المصفوفات
- المصفوفات الديناميكية
- القوائم المترابطة (linked lists)
- المكدسات (stacks)
- الطوابير (queues)
تعلّم أولًا
73 دقيقة قراءة · 5 ساعة تدريب (تقدير)
مخرجات التعلم
- Implement a dynamic array and explain amortized O(1) append.
- Implement a singly linked list with insert, remove, and search.
- Implement a stack and a queue and pick one for a given problem.
- Compare array-based and linked structures by operation cost.
الدروس
- 01المصفوفات في الذاكرة12 د قراءة
- 02المصفوفات الديناميكية وتغيير الحجم10 د قراءة
- 03القوائم المترابطة (Linked lists)11 د قراءة
- 04المكدسات (Stacks)9 د قراءة
- 05الطوابير (Queues)10 د قراءة
- 06الاختيار: ArrayList مقابل LinkedList مقابل ArrayDeque11 د قراءة
- 07عرض عملي: بناء MyArrayList ومشاهدته وهو يغيّر حجمه10 د قراءة
المختبر والتمارين
Lab
BEG-040-LAB1 · Build your own
Outcomes: 1–4 · Time: ~5 h
- Implement
MyArrayList<T>(add,get,remove(int),size) with doubling growth. - Implement
MyLinkedList<T>(addFirst,addLast,insert,remove,contains). - Implement a stack and a queue (any base) and write a bracket-matching checker with your stack.
- Write the Big O of each method in a comment above it.
Acceptance: passing tests (plain main checks are fine until BEG-045); complexity of each method documented.
Exercises (assessment: implementation plus 4 problems)
| ID | Outcome | Task |
|---|---|---|
| BEG-040-EX01 | 1 | A dynamic array has capacity 4 and doubles when full. Count the copies done while adding 17 items, starting empty. |
| BEG-040-EX02 | 1 | Explain in three sentences why append is amortized O(1) and not worst-case O(1). |
| BEG-040-EX03 | 2 | Draw the nodes before and after removing the middle item of A -> B -> C; write the one line that rewires. |
| BEG-040-EX04 | 3 | Use a stack to check whether "([)]" and "{[()]}" are balanced. |
| BEG-040-EX05 | 3 | Choose stack or queue: undo history; print jobs; browser back button; customers at a counter. |
| BEG-040-EX06 | 4 | Fill in the cost (O(1) or O(n)) for ArrayList and a singly linked list: get by index, add at end, add at front, remove at front. |
أظهر الحلول
- EX01 Resizes happen when adding items 5, 9, and 17 (to capacities 8, 16, 32): 3 copies, moving 4 + 8 + 16 = 28 items in total.
- EX02 Most appends write one slot. Occasionally one append copies all items (O(n)). The total over
nappends is about 2n, so on average each is O(1), but a single append can be O(n). - EX03 Before: A -> B -> C. After: A -> C.
a.next = b.next;(withathe node beforeb). - EX04
"([)]"is not balanced ()meets[on top);"{[()]}"is balanced and the stack ends empty. - EX05 Stack; queue; stack; queue.
- EX06
ArrayList: O(1), O(1) amortized, O(n), O(n). Singly linked list: O(n), O(n) without a tail reference (O(1) with one), O(1), O(1).
الاختبار
Outcomes: O1 dynamic array · O2 linked list · O3 stack and queue · O4 compare structures.
اختبار ذاتي لك: لا توجد درجات، ولا يُحفظ أو يُرسل أي شيء. اختر إجابة ثم تحقق منها، ويمكنك المحاولة مرة أخرى كما تشاء.
الجزء العملي
Implementation of the lab (MyArrayList, MyLinkedList, stack, queue, bracket checker) plus 4 problems (BEG-040-EX01, EX04, EX05, EX06). Pass: tests pass, complexity documented, and at least 3 of the 4 problems correct. Exercises EX02 and EX03 are also part of the module.
أخطاء شائعة
Losing the list's tail on removal; resizing by +1 instead of doubling.
التقييم
Implementation plus 4 problems.
الصلة بالمسار الوظيفي
Queues reappear as message queues (MID-026).