برای موفقیت در دنیای برنامه‌نویسی جاوا از ساختمان داده‌ها غافل نشوید

مطلب پیشنهادی

آشنایی با مهم‌ترین الگوهای زیرساختی

چرا یادگیری ساختمان داده‌ها برای هر برنامه‌نویسی ضروری است؟

مطلب پیشنهادی

جاوا، محبوب قدیمی

۹ سایت آموزش رایگان جاوا به زبان فارسی

ساختمان داده‌ها در جاوا چیست و چرا به آن نیاز داریم؟

ساختمان داده‌ها به روش‌های مختلف ذخیره‌سازی و سازمان‌دهی داده‌ها در سیستم‌های کامپیوتری اشاره دارد. به‌طوری که بتوان از داده‌ها به‌شکل کارآمدی استفاده کرد. ساختمان‌ داده‌ها ابزاری برای مدیریت کارآمد حجم زیادی از داده‌ها هستند تا بتوان به‌شکل بهینه به داده‌ها دسترسی پیدا کرده و آن‌ها را ویرایش کرد. ساختمان‌ داده‌ها کمک می‌کنند تا الگوریتم‌هایی با پیچیدگی زمانی کمتر و مرتبه اجرایی بهتر را بنویسیم. به‌طور کلی هنگام نوشتن یک الگوریتم بهینه باید به دو معیار حافظه و زمان مصرفی دقت کنیم تا خروجی کار قابل قبول باشد. به همین دلیل باید اطلاعات کاملی در ارتباط با انواع مختلف ساختمان داده‌ها داشته باشیم. ساختمان داده‌ها در زبان‌های برنامه‌نویسی مثل جاوا، ابزاری کارآمد برای مدیریت حجم زیادی از داده‌ها هستند و تقریبا در بیشتر برنامه‌های کاربردی بزرگ مثل، سیستم‌عامل‌ها، برنامه‌های کاربردی هوش مصنوعی، طراحی کامپایلرها و غیره از آن‌ها استفاده می‌شود. 

امروزه، برنامه‌های کاربردی با حجم زیادی از داده‌ها در ارتباط هستند و همین موضوع پیچیدگی این برنامه‌ها را دوچندان کرده و چالش‌های زیادی برای برنامه‌های کاربردی و برنامه‌نویسان ایجاد کرده است که از مهم‌ترین آن‌ها به موارد زیر باید اشاره کرد:

• سرعت پردازش (Processing Speed): به همان نسبتی که حجم داده‌ها بیشتر می‌شود، سرعت مدیریت و پردازش هم باید افزایش پیدا کند. درست است که پردازنده‌های امروزی قادر به پردازش حجم زیادی از داده‌ها در کمترین زمان هستند، اما برای دستیابی به چنین هدفی باید الگوریتم‌های کارآمدی نوشته شود. 
• جست‌و‌جوی داده‌ها (Searching Data): فروشگاه‌ آنلاینی را تصور کنید که بیش از 200 هزار کالا دارد. اگر برنامه‌ای قصد جست‌و‌جو در ارتباط با یک کالای خاص بر مبنای شرایط خاصی را داشته باشد، برنامه باید مشخصات 200 هزار کالا را بررسی کند تا نتیجه را بازگرداند. این‌کار سرعت جست‌وجو را کم می‌کند. 
• چندین درخواست در یک زمان یکسان (Multiple requests at the same time): تصور کنید میلیون‌ها کاربر در حال جست‌و‌جوی داده‌ها به‌شکل همزمان در وب سرور هستند، طبیعی است احتمال بروز مشکل برای سرور افزایش پیدا می‌کند.

برای حل مشکلات فوق، توسعه‌دهندگان از ساختمان داده‌ها در زبان‌های برنامه‌نویسی مثل جاوا استفاده می‌کنند. در ساختمان داده‌های جاوا، داده‌ها به گونه‌ای ذخیره و مدیریت می‌شوند که دسترسی به داده‌ها در هنگام جست‌و‌جو در کوتاه‌ترین زمان امکان‌پذیر شود. 

مطلب پیشنهادی

سازمان‌دهی و مرتب‌سازی سریع داده‌ها

آشنایی با انواع درخت‌ها در ساختمان داده‌ها

ساختمان داده‌ها در جاوا چه مزیتی دارد؟

همان‌‌گونه که اشاره کردیم، استفاده از ساختمان داده‌ها به مدیریت بهتر داده‌ها کمک می‌کنند و برخی از مشکلات اشاره‌شده در پاراگراف قبل را برطرف می‌کنند. با این‌حال، برنامه‌نویسان جاوا به دلایل زیر از ساختمان داده‌ها در جاوا استفاده می‌کنند:

• عملکرد (Efficiency): ساختمان داده در جاوا با ساختارمند کردن داده‌ها عملکرد برنامه‌های کاربردی را به‌شکل قابل توجهی بهبود می‌بخشد، زیرا اجازه می‌دهند داده‌ها با کمترین فضای ممکن ذخیره‌سازی شوند و با سرعت زیادی پردازش شوند. 
• قابلیت استفاده مجدد (Reusability): قابلیت استفاده مجدد از داده‌ها یکی از مهم‌ترین دلایل استفاده از ساختمان داده‌ها است. بعد از پیاده‌سازی یک ساختمان داده خاص می‌توان آن‌را به دفعات در بخش‌های مختلف یک برنامه کاربردی استفاده کرد. علاوه بر این، امکان تعریف ساختمان داده در کتابخانه‌ها و به‌کارگیری آن به روش‌های مختلف در برنامه‌های کاربردی مختلف وجود دارد. 
• انتزاعی کردن (Abstraction): در جاوا نوع انتزاعی داده‌ها ADT سرنام Abstract Data Type  برای مشخص کردن ساختمان داده استفاده می‌شود. نوع انتزاعی داده‌ها بالاترین سطح از پنهان‌سازی جزئیات را فراهم می‌کند. در روش مذکور توسعه‌دهندگان می‌توانند از ساختمان داده‌ها در جاوا با کمک واسط‌ها (Interface) در برنامه‌های کاربردی استفاده می‌کنند، بدون این‌که بدون دلیل درگیر جزئیات پیاده‌سازی ساختمان داده‌ها شوند. 

مطلب پیشنهادی

خطوط انتقال داده‌ها

یک مهندس داده به چه مهارت‌ها و دانشی نیاز دارد؟

طبقه‌بندی ساختمان داده‌ها در جاوا

به‌طور کلی ساختمان داده‌ها در زبان برنامه‌نویسی جاوا به دو گروه ساختمان داده‌های خطی (Linear Data Structures) و ساختمان داده‌های غیرخطی (Non Linear Data Structure) که برخی منابع به آن ساختمان داده‌های سلسله‌مراتبی (Hierarchical Data Structures) می‌گویند، تقسیم می‌شوند که هر یک زیرمجموعه‌های خاص خود را دارند. شکل 1 طبقه‌بندی فوق را نشان می‌دهد. 

شکل 1

• ساختارهای داده خطی (Linear Data Structures): در یک ساختار داده خطی، همه عناصر به ترتیب خطی یا ترتیبی مرتب می‌شوند. ساختار داده خطی یک ساختار داده تک‌سطحی (Single Level Data Structure) است که در آن عناصر به‌ترتیب پشت‌سرهم قرار می‌گیرند. 
• ساختارهای داده غیرخطی (Non-Linear Data Structures): در یک ساختار داده غیرخطی، داده‌ها مانند ساختارهای داده خطی به‌شکل متوالی مرتب و ذخیره‌سازی نمی‌شوند. به همین دلیل ساختارهای داده غیرخطی ساختار داده چند سطحی هستند.

شکل 2 تفاوت این دو ساختار را نشان می‌دهد.

شکل 2

مطلب پیشنهادی

جاوا یک زبان برنامه‌نویسی سازمانی همچنان مقتدر

انواع ساختمان داده‌ها در جاوا

ساختمان داده‌های اصلی در زبان برنامه‌نویسی جاوا، موارد زیر هستند:

•  آرایه‌ها (Arrays)
•  لیست‌های پیوندی (Linked Lists)
•  پشته (Stack)
•  صف (Queue)
•  نمودار (Graph)
•  مجموعه (Set)

ساختمان داده آرایه در جاوا 

آرایه (Array) یک ساختمان داده خطی و ایستا است که گروهی از عناصر مشابه را نشان می‌دهد که توسط اندیس‌ها (Index) می‌توان به آن‌ها دسترسی پیدا کرد. معمولاً، اندازه آرایه در جاوا قبل از ذخیره داده‌ها در آن مشخص می‌شود. اولین آدرس آرایه متعلق به اولین عنصر است و آخرین آدرس به آخرین عنصر آرایه تعلق دارد. 

آرایه ساده‌ترین ساختار داده است که مجموعه‌ای از عناصر هم‌نوع است و با یک نام مشترک به آن ارجاع داده می‌شود. آرایه‌ها در مکان‌های به‌هم‌پیوسته حافظه ذخیره‌سازی می‌شوند و تخصیص داده‌ها از کوچک‌ترین عنصر مکان حافظه تخصیص‌داده‌شده به آرایه انجام می‌شود.  اولین آدرس آرایه به اولین عنصر و آخرین آدرس به آخرین عنصر آرایه اشاره دارد. آرایه‌ها دارای داده‌های ساده با نوع داده یکسان مانند عدد صحیح (Integer)، اعشار (Float) یا نوع‌های داده‌ای تعریف‌شده توسط کاربر (User Defined Data type) هستند. همچنین، همه عناصر اندازه‌ای یکسان دارند. در هنگام استفاده از آرایه‌ها باید به چند نکته مهم دقت کنید:

•  آرایه‌ها می‌توانند عناصر داده‌ای از انواع ساده و مشابه مانند int یا float یا نوع‌های داده‌ای تعریف‌شده توسط کاربر مانند ساختارها و اشیاء باشند.
•  آرایه‌ها در جاوا به‌عنوان اشیاء در نظر گرفته می‌شوند.
•  نمایه‌سازی (اندیس‌گذاری) مقادیر آرایه‌ها با عدد صفر آغاز می‌شود. 
•  قبل از استفاده از آرایه‌ها باید آن‌ها را برای ذخیره‌سازی اطلاعات تعریف کنیم. 
• مکان ذخیره‌سازی آرایه‌ها در جاوا به‌صورت تخصیص پویا در ناحیه Heap انجام می‌شود. 
•  طول آرایه‌ها با استفاده از متد Length انجام می‌شود. 
•  اندازه آرایه باید به‌صورت یک مقدار صحیح (Int) باشد.
•  امکان دسترسی تصادفی به عناصر آرایه در جاوا وجود دارد. 

مطلب پیشنهادی

یک زبان بدون توقف و دائما در حال رشد

آیا سرمایه‌گذاری روی یادگیری زبان برنامه‌نویسی جاوا (java) ارزشمند است؟

آرایه‌ها در زبان جاوا می‌توانند تک‌بعدی، دوبعدی یا چندبعدی باشند. هرچه تعداد بعدهای آرایه بیشتر شود به همان نسبت پیچیدگی تعریف و دسترسی به داده‌ها بیشتر شده و حافظه قابل توجهی مصرف می‌شود. شکل 3 آرایه‌های تک‌بعدی را نشان می‌دهد.

در  شکل 3 و سمت چپ، اولین عنصر و اندیس و در سمت راست، آخرین عنصر و اندیس را مشاهده می‌کنید. دقت کنید دسترسی به عناصر آرایه در شکل 3 با مقدار صفر آغاز شده و با مقدار 4 پایان می‌پذیرد. در این‌جا اندیس صفر به مقدار 126، اندیس یک به مقدار 32، اندیس دو به مقدار 230، اندیس سه به مقدار 21 و اندیس چهار به مقدار 200 اشاره دارد. 

 شکل 3

به‌طور معمول، زمانی از آرایه‌ها استفاده می‌کنیم که تعداد عناصر و اندازه آن‌را از قبل بدانیم، زیرا حافظه قبل از پردازش برای آرایه‌ها رزرو می‌شود. به همین دلیل، آرایه‌ها در گروه ساختارهای داده ایستا قرار می‌گیرند. یکی از نکات مهمی که هنگام استفاده از آرایه‌ها باید به آن دقت کنید پیچیدگی‌های زمانی است. پیچیدگی زمانی برای انجام عملیات مختلف روی آرایه‌ها به‌شرح زیر است: 

• دسترسی به عناصر : O(1)
• جست‌و‌جوی متوالی: O(n)
• جست‌وجوی دودویی (Binary Search) در صورتی که آرایه مرتب باشد: O(long n)
• اضافه کردن: O(n)
• حذف کردن: O(n)

لیست پیوندی در جاوا 

لیست پیوندی (Linked List) در زبان جاوا یک ساختمان داده خطی و پویا است که مجموعه‌ای از انواع مشابه عناصر داده‌ای را که گره (Node) نام دارند میزبانی می‌کند. این نوع ساختمان داده دو نوع داده را به‌طور همزمان ذخیره‌سازی می‌کند. نوع اول مقدار واقعی است که در برنامه استفاده می‌شود و نوع دوم اشاره‌گری به مکان عنصر بعدی در لیست است. آخرین عنصر به تهی (Null) اشاره دارد و به‌معنای اتمام لیست پیوندی است. گره اول در لیست پیوندی سر (Head) و گره آخر انتها (Tail) نام دارد. 

لیست‌های پیوندی در جاوا با هدف برطرف کردن برخی از مشکلات آرایه‌ها طراحی شدند. به‌طور مثال، در این نوع ساختمان داده نیازی به تعریف تعداد عناصر قبل از استفاده از آن‌ها نیست، از این‌رو فرآیند تخصیص حافظه می‌تواند در زمان پردازش و مطابق با نیاز انجام شود. علاوه بر این، عملیات درج و حذف عناصر در لیست‌های پیوندی به‌شکل ساده‌تری انجام می‌شود. در جاوا لیست‌های پیوندی می‌توانند یک طرفه، دو طرفه و حلقوی باشند. 

لیست پیوندی یک طرفه (Singly Linked List)

• همان‌گونه که در شکل 4 مشاهده می‌کنید، افزودن مقادیر در لیست‌های پیوندی مبتنی بر یک حرکت روبه‌جلو و تک‌جهتی است. این لیست پیوندی یک گره و یک اشاره‌گر واحد دارد که به گره بعد اشاره می‌کند.

 شکل 4

لیست پیوندی دو طرفه (Doubly Linked List)

• لیست پیوندی دو طرفه رو‌به‌جلو و روبه‌عقب می‌تواند داده‌ها را دریافت کند. به همین دلیل دو اشاره‌گر دارد که یکی به گره قبلی و دیگری به گره بعدی اشاره دارد. در لیست‌های پیوندی دو طرفه، امکان پیمایش از دو طرف لیست وجود دارد. شکل 5 لیست‌های پیوندی دو طرفه را نشان می‌دهد. 

شکل 5

لیست پیوندی حلقوی (Circular Linked List)

• در لیست پیوندی حلقوی گره‌ها به‌صورت دوار با هم در ارتباط هستند. در این لیست پیوندی هیچ گره تهی وجود ندارد و هر گره‌ را می‌توان به عنوان گره اول تعریف کرد. همچنین، به این نکته مهم دقت کنید که لیست‌های پیوندی‌ دو طرفه گزینه مناسبی برای پیاده‌سازی صف‌‌های دوار هستند. شکل 6 یک لیست پیوندی حلقوی را نشان می‌دهد.

شکل 6

پیچیدگی‌ زمانی عملیات مختلف روی لیست‌های پیوندی به‌شرح زیر است :

• پیمایش عناصر: O(n)
• جست‌و‌جو یک عنصر: O(n)
• اضافه کردن: O(1)
• حذف کردن: O(1)

از عملیات رایج قابل اجرا روی لیست‌های پیوندی باید به ادغام دو لیست پیوندی، تقسیم‌بندی لیست‌ها و معکوس کردن لیست اشاره کرد. 

پشته در زبان برنامه‌نویسی جاوا

پشته (Stack) یک ساختمان داده انتزاعی در جاوا است. پشته مجموعه‌ای از اشیاء است که فرآیند افزودن و حذف به آن‌ها بر مبنای اصل «آخرین ورودی، اولین خروجی» (‌ LIFO) سرنام Last In First Out انجام می‌شود. اشیاء را می‌توان در هر زمان به پشته اضافه کرد، اما فقط آخرین شیء اضافه‌شده در هر زمان قابل حذف است. هنگامی‌که پشته به‌عنوان آرایه یا یک لیست پیوندی تعریف ‌شود، تمامی ویژگی‌های آرایه یا لیست پیوندی را به ارث می‌برد. شکل 7 پشته را نشان می‌دهد. 

شکل 7

دقت کنید که پشته در زبان برنامه‌نویسی جاوا در اصل یک لیست مرتب است که تنها از عملیات درج و حذف تنها از یک بخش و آن هم بالای پشته پشتیبانی می‌کند. به‌طور کلی، پشته‌ها در انجام عملیاتی مثل فراخوانی توابع تودرتو، حل مسئله ماز (Maze)، تطابق پرانتزها و موارد این‌چنینی استفاده می‌شوند. عملیاتی که روی پشته انجام می‌شوند به‌شرح زیر هستند: 

• ()Push: عنصری را به بالای پشته اضافه می‌کند.
• ()Pop : عنصری از بالای پشته را حذف می‌کند و عنصر حذف‌شده از پشته را باز می‌گرداند.
• ()Peek: بدون حذف عنصر بالای پشته، آن‌را اعلام یا بازیابی می‌کند. گاهی اوقات به این متد ()Top گفته می‌شود.
• صف (Queue) در زبان برنامه‌نویسی جاوا

صف یکی دیگر از ساختمان‌ داده‌های پرکاربرد در جاوا است که نقطه مقابل پشته است. صف مجموعه‌ای از اشیاء است که بر مبنای اصل «اولین ورودی، اولین خروجی» (FIFO) سرنام First In First Out فرآیند اضافه و حذف اشیاء را انجام می‌دهد. در ساختمان داده صف، فرآیند اضافه کردن همیشه از انتها (Rear) و حذف‌ها از ابتدای (Front) صف انجام می‌شوند. شکل 8 ساختمان داده صف در جاوا را نشان می‌دهد.

شکل 8

 از عملیات رایج روی صف‌ها به موارد زیر باید اشاره کرد: 

• ()Enqueue: افزودن عنصری به انتهای صف.
• ()Dequeue: بازگرداندن اولین عنصر صف و حذف آن.

به‌طور معمول از صف برای جست‌وجوی‌ اول‌سطح (Breadth First Searching) در ساختمان داده‌های خاص مثل درخت‌ها و گراف‌ها استفاده می‌شود. صف‌ها در مدیریت زمان‌بندی پردازه‌ها در سیستم‌عامل‌های چند‌وظیفه‌ای، الگوریتم‌های زمان‌بندی، الگوریتم زمان‌بندی نوبت گردشی و موارد مشابه کاربرد دارند. همچنین، گزینه مناسبی در انتقال داده‌ها بین دو فرآیند به‌صورت نامتقارن (Asynchronous) هستند. 

توسعه‌دهندگان می‌توانند صف‌ها را به روش‌های مختلف در برنامه‌های کاربردی استفاده کنند. با این‌حال، دو نوع صف پر‌کاربرد در جاوا صف حلقوی (Circular Queue) و صف دو طرفه (Double Ended Queues) است. صف‌های حلقوی در یک مسیر دوار پیاده‌سازی و تعریف می‌شوند. مزیتی که این مدل ساختمان داده دارد این است که مشکل فضاهای استفاده‌نشده در صف‌های ساده و خطی را برطرف می‌کند. صف دو طرفه در جاوا اجازه می‌دهد عناصر را از هر دو طرف صف حذف و اضافه کرد، اما امکان انجام این‌کار از وسط صف وجود ندارد. 

ساختمان داده گراف (Graph) در جاوا

گراف یک ساختمان داده غیر‌خطی در زبان برنامه‌نویسی جاوا است که از مولفه‌های زیر ساخته شده است: 

•  مجموعه‌ای متناهی از رئوس (Vertice) که به‌عنوان گره (Node) شناخته می‌شوند.
•  یال‌ها (Edge) که با مجموعه محدودی از جفت‌های مرتب به‌شکل (e, v) نشان داده می‌شوند. در این‌جا v نشان‌دهنده تعداد رئوس و e نشان‌دهنده تعداد یال‌ها است.
• ساختمان داده گراف در جاوا بر اساس پارامترهایی که دارد به دو گروه گراف مسیر (Direction Graph) و گراف وزن (Weight Graph) تقسیم می‌شود.
• در ساختمان داده گراف مسیر، گراف‌ها به دو گروه گراف جهت‌دار(Directed Graph) و گراف بدون جهت (Undirected Graph) تقسیم می‌شوند. 
• گراف جهت‌دار مجموعه‌ای از گره‌ها یا رئوس متصل به یک‌دیگر است که همه یال‌ها دارای جهتی از یک راس به راس دیگر هستند. 
• در ساختمان داده گراف وزن، گراف‌ها به دو گروه گراف وزن‌دار(Weighted Graph) و گراف بدون وزن (Unweighted Graph) تقسیم می‌شوند. 
• ساختمان داده گراف وزن‌دار، گرافی است که هر یال وزن دارد. این گراف به‌نام گراف برچسب‌دار (Labeled Graph) نیز شناخته می‌شود. 
• در ساختمان داده گراف بدون وزن هیچ وزنی برای یال‌های در نظر گرفته نمی‌شود.

مجموعه (Set)

مجموعه، ساختمان داده‌ای خاص است که تفاوت مهمی نسبت به نمونه‌های دیگر دارد، به‌طوری که از مقادیر تکراری (Duplicate Value) پشتیبانی نمی‌کند. این ساختمان داده در جاوا برای ذخیره‌سازی عناصر منحصربه‌فرد مانند شناسه کاربری یکتا (ID) استفاده می‌شود (شکل 9). ساختمان داده مجموعه را می‌توان به روش‌های مختلفی در جاوا پیاده‌سازی کرد که از مهم‌ترین آن‌ها باید به مجموعه درهم‌سازی پیوندی (Linked Hash Set)، مجموعه درهم‌سازی (Hash Set) و مجموعه درخت (Tree Set) اشاره کرد. این ساختمان‌ داده‌ها از طریق واسط‌های برنامه‌نویسی کاربردی جاوا (Java Collection API) تعریف می‌شوند. 

شکل 9

کلام آخر

سعی کردیم مهم‌ترین ساختارهای داده ذخیره‌سازی و سازمان‌دهی داده‌ها در زبان برنامه‌نویسی جاوا را به شما معرفی کنیم. در این مقاله، با برخی از ساختارهای داده مهم جاوا مانند آرایه‌ها، لیست‌های پیوندی، پشته‌ها، صف‌ها، نمودارها و مجموعه‌ها آشنا شدیم. اکنون که اطلاعات اولیه‌ای در ارتباط با ساختمان داده‌ها در جاوا دارید و می‌دانید هر یک از این ساختمان داده‌ها در جاوا چه ویژگی‌هایی دارند و برای انجام چه کارهایی مناسب هستند، باید کمی وقت صرف کنید و نحوه پیاده‌سازی عملی هر یک از این ساختمان داده‌ها را یاد بگیرید.