ساختار داده‌ها چیست؟
نوع داده انتزاعی Abstraction Data Type -ADT
- خطی یا Linear: شامل ساختارهایی چون لیست و صف و پشته است: List ,Queue,Stack
- درختی یا Tree-Like: درخت باینری ، درخت متوازن و B-Trees
- Dictionary : شامل یک جفت کلید و مقدار است در جدول هش
- بقیه: گراف‌ها، صف الویت، bags, Multi bags, multi sets
| (void Add(object | افزودن المان به آخر لیست |
| (void Remove(object | حذف یک المان خاص از لیست |
| ()void Clear | حذف کلیه المان‌ها |
| ( bool Contains(object | شامل این داده میشود یا خیر؟ |
| ( void RemoveAt(int | حذف یک المان بر اساس جایگاه یا اندیسش |
| (void Insert(int, object | افزودن یک المان در جایگاهی (اندیس) خاص بر اساس مقدار position |
| (int IndexOf(object | اندیس یا جایگاه یک عنصر را بر می‌گرداند |
| [this[int | ایندکسر ، برای دستریس به عنصر در اندیس مورد نظر |
لیست‌های ایستا static Lists
public class CustomArrayList<T>
{
private T[] arr;
private int count;
public int Count
{
get
{
return this.count;
}
}
private const int INITIAL_CAPACITY = 4;
public CustomArrayList(int capacity = INITIAL_CAPACITY)
{
this.arr = new T[capacity];
this.count = 0;
} public void Add(T item)
{
GrowIfArrIsFull();
this.arr[this.count] = item;
this.count++;
}
public void Insert(int index, T item)
{
if (index > this.count || index < 0)
{
throw new IndexOutOfRangeException(
"Invalid index: " + index);
}
GrowIfArrIsFull();
Array.Copy(this.arr, index,
this.arr, index + 1, this.count - index);
this.arr[index] = item;
this.count++;
}
private void GrowIfArrIsFull()
{
if (this.count + 1 > this.arr.Length)
{
T[] extendedArr = new T[this.arr.Length * 2];
Array.Copy(this.arr, extendedArr, this.count);
this.arr = extendedArr;
}
}
public void Clear()
{
this.arr = new T[INITIAL_CAPACITY];
this.count = 0;
} 
برای پیاده سازی آن به دو کلاس نیاز داریم. کلاس ListNode برای نگهداری هر المان و اطلاعات المان بعدی به کار می‌رود که از این به بعد به آن Node یا گره می‌گوییم و دیگری کلاس <DynamicList<T برای نگهداری دنباله ای از گره‌ها و متدهای پردازشی آن.
public class DynamicList<T>
{
private class ListNode
{
public T Element { get; set; }
public ListNode NextNode { get; set; }
public ListNode(T element)
{
this.Element = element;
NextNode = null;
}
public ListNode(T element, ListNode prevNode)
{
this.Element = element;
prevNode.NextNode = this;
}
}
private ListNode head;
private ListNode tail;
private int count;
// …
} از آن جا که نیازی نیست کاربر با کلاس ListNode آشنایی داشته باشد و با آن سر و کله بزند، آن را داخل همان کلاس اصلی به صورت خصوصی استفاده میکنیم. این کلاس دو خاصیت دارد؛ یکی برای المان اصلی و دیگر گره بعدی. این کلاس دارای دو سازنده است که اولی تنها برای عنصر اول به کار می‌رود. چون اولین بار است که یک گره ایجاد میشود، پس باید خاصیت NextNode یعنی گره بعدی در آن Null باشد و سازنده‌ی دوم برای گره‌های شماره 2 به بعد به کار می‌رود که همراه المان داده شده، گره قبلی را هم ارسال میکنیم تا خاصیت NextNode آن را به گره جدیدی که می‌سازیم مرتبط سازد. سه خاصیت کلاس اصلی به نام‌های Count,Tail,Head به ترتیب برای اشاره به اولین گره، آخرین گره و تعداد گره‌ها، به کار می‌روند که در ادامه کد آن‌را در زیر می‌بینیم:
public DynamicList()
{
this.head = null;
this.tail = null;
this.count = 0;
}
public void Add(T item)
{
if (this.head == null)
{
this.head = new ListNode(item);
this.tail = this.head;
}
else
{
ListNode newNode = new ListNode(item, this.tail);
this.tail = newNode;
}
this.count++;
} سازنده مقدار دهی پیش فرض را انجام میدهد. در متد Add المان جدیدی باید افزوده شود؛ پس چک می‌کند این المان ارسالی قرار است اولین گره باشد یا خیر؟ اگر head که به اولین گره اشاره دارد Null باشد، به این معنی است که این اولین گره است. پس اولین سازنده‌ی کلاس ListNode را صدا می‌زنیم و آن را در متغیر Head قرار میدهیم و چون فقط همین گره را داریم، پس آخرین گره هم شناخته میشود که در tail نیز قرار می‌گیرد. حال اگر فرض کنیم المان بعدی را به آن بدهیم، اینبار دیگر Head برابر Null نخواهد بود. پس دومین سازنده‌ی ListNode صدا زده میشود که به غیر از المان جدید، باید آخرین گره قبلی هم با آن ارسال شود و گره جدیدی که ایجاد میشود در خاصیت NextNode آن نیز قرار بگیرد و در نهایت گره ایجاد شده به عنوان آخرین گره لیست در متغیر Tail نیز قرار می‌گیرد. در خط پایانی هم به هر مدلی که المان جدید به لیست اضافه شده باشد متغیر Count به روز میشود.
public T RemoveAt(int index)
{
if (index >= count || index < 0)
{
throw new ArgumentOutOfRangeException(
"Invalid index: " + index);
}
int currentIndex = 0;
ListNode currentNode = this.head;
ListNode prevNode = null;
while (currentIndex < index)
{
prevNode = currentNode;
currentNode = currentNode.NextNode;
currentIndex++;
}
RemoveListNode(currentNode, prevNode);
return currentNode.Element;
}
private void RemoveListNode(ListNode node, ListNode prevNode)
{
count--;
if (count == 0)
{
this.head = null;
this.tail = null;
}
else if (prevNode == null)
{
this.head = node.NextNode;
}
else
{
prevNode.NextNode = node.NextNode;
}
if (object.ReferenceEquals(this.tail, node))
{
this.tail = prevNode;
}
} برای حذف یک گره شماره اندیس آن گره را دریافت میکنیم و از Head، گره را بیرون کشیده و با خاصیت nextNode آنقدر به سمت جلو حرکت میکنیم تا متغیر currentIndex یا اندیس داده شده برابر شود و سپس گره دریافتی و گره قبلی آن را به سمت تابع RemoveListNode ارسال میکنیم. کاری که این تابع انجام میدهد این است که مقدار NextNode گره فعلی که قصد حذفش را داریم به خاصیت Next Node گره قبلی انتساب میدهد. پس به این ترتیب پیوند این گره از لیست از دست می‌رود و گره قبلی به جای اشاره به این گره، به گره بعد از آن اشاره می‌کند. مابقی کد از قبیل جست و برگردان اندیس یک عنصر و ... را به خودتان وگذار می‌کنم.
در روش‌های بالا ما خودمان 2 عدد ADT را پیاده سازی کردیم و متوجه شدیم برای دخیره داده‌ها در حافظه روش‌های متفاوتی وجود دارند که بیشتر تفاوت آن در مورد استفاده از حافظه و کارآیی این روش هاست.
لیست‌های پیوندی دو طرفه Doubly Linked_List
لیست‌های پیوندی بالا یک طرفه بودند و اگر ما یک گره را داشتیم و می‌خواستیم به گره قبلی آن رجوع کنیم، اینکار ممکن نبود و مجبور بودیم برای رسیدن به آن از ابتدای گره حرکت را آغاز کنیم تا به آن برسیم. به همین منظور مبحث لیست‌های پیوندی دو طرفه آغاز شد. به این ترتیب هر گره به جز حفظ ارتباط با گره بعدی از طریق خاصیت NextNode، ارتباطش را با گره قبلی از طریق خاصیت PrevNode نیز حفظ می‌کند.
این مبحث را در اینجا می‌بندیم و در قسمت بعدی آن را ادامه میدهیم.
