ساختمان داده در جاوا — از صفر تا صد

در این مقاله به بحث ساختمان داده در جاوا (Java Data Structures) و انواع آن پرداخته شده است. انواع ساختمان داده در جاوا به دو دسته کلی ساختمان داده خطی و ساختمان داده غیر خطی در جاوا تقسیم می‌شود. از جمله ساختمان داده‌های خطی در جاوا می‌توان به آرایه، لیست پیوندی، پشته و ساختمان داده صف اشاره کرد. همچنین ساختما‌ن‌های داده غیرخطی شامل درخت دودویی، ساختمان داده پیشوندی، هرمی (Heap) و گراف می‌شود. در طول بخش‌های مختلف این نوشتار، مثال‌های متعددی به زبان جاوا برای هر یک از انواع ساختمان داده ارائه شده است.

از آن‌جایی که ساختمان داده‌ها (Data Structures) هسته اصلی هر زبان برنامه نویسی به حساب می‌آیند و انتخاب یک ساختمان داده خاص بر کارایی و عملکرد برنامه‌های زبان برنامه نویسی جاوا (Java) تأثیرات فراوانی می‌گذارد، بنابراین یادگیری ساختمان داده‌های مختلف موجود در جاوا از الزامات این زبان برنامه نویسی محسوب می‌شود. در هنگام برنامه نویسی، از ساختمان داده برای ذخیره و سازماندهی داده‌ها استفاده می‌شود، سپس الگوریتم‌ها (Algorithm) برای ویرایش و طراحی ساختمان داده‌ها مورد استفاده قرار می‌گیرند. از این رو به دلیل اهمیت بالای ساختمان داده و همچنین برنامه نویسی همه‌منظوره جاوا، در مقاله «ساختمان داده در جاوا» به بررسی ساختمان داده‌ها در این زبان برنامه نویسی پر کاربرد پرداخته شده است.

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

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

همچنین، استفاده از ساختمان داده مناسب باعث ایجاد امکان طراحی الگوریتم‌های بهتری برای داده‌های مورد نظر می‌شود. ساختمان داده‌ها در جاوا تقریباً در هر زمینه‌ای از علوم کامپیوتر (Computer Science) مورد استفاده قرار می‌گیرند که برخی از آن‌ها شامل گرافیک کامپیوتری (Computer Graphic)، سیستم عامل‌ها (Operating System | OS)، هوش مصنوعی (Artificial Intelligence | AI)، طراحی کامپایلر (Compiler Design) و بسیاری از موارد دیگر می‌شوند.

در بخش بعدی مقاله «ساختمان داده در جاوا» به این موضوع پرداخته شده است که چرا به ساختمان داده‌ها در جاوا نیاز است؟

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

از آن‌جایی که مقدار داده‌ها در پروژه‌ها به سرعت رو به افزایش است، برنامه‌ها روز به روز پیچیده‌تر می‌شوند و مشکلاتی برای آن‌ها پیش می‌آید که برخی از این مشکلات در ادامه فهرست شده‌اند:

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

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

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

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

همچنین، ساختمان داده‌های جاوا مزایای بسیاری هم دارند که در این بخش به آن‌ها اشاره شده است:

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

بخش بعدی مقاله «ساختمان داده در جاوا» به طبقه‌بندی انواع گوناگون ساختمان داده‌ها در جاوا اختصاص داده شده است.

طبقه بندی ساختمان داده در جاوا چگونه است؟

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

• ساختمان داده‌های خطی
  • ساختمان داده ایستا یا ثابت (Static)
    • آرایه (Array)
  • ساختمان داده پویا (Dynamic)
    • لیست پیوندی (Linked List)
    • پشته (Stack)
    • صف (Queue)
• ساختمان داده‌های غیر خطی
  • درخت (Tree)
    • درخت دودویی (Binary Tree)
    • درخت جست و جوی دودویی (Binary Search tree | BST)
    • درخت پیشوندی (Trie Tree)
    • هرم (Heap)
  • گراف (Graph)
  • مجموعه (Set)
  • جدول درهم‌سازی (Hash Table)

همچنین، انواع ساختمان داده‌های اصلی در نمودار زیر ارائه شده‌اند:

بخش‌های بعدی مقاله «ساختمان داده در جاوا» به بررسی هر یک از انواع ساختمان داده‌های فوق اختصاص داده شده‌اند. در بخش بعدی، ابتدا ساختمان داده‌های خطی شرح داده شده است.

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

ساختمان داده خطی در جاوا نوعی از ساختمان داده‌ها به حساب می‌آید که عناصر آن به صورت متوالی و به ترتیب قرار گرفته‌اند. ساختمان داده خطی یک ساختمان داده تک سطحی (Single Level Data Structure) است. در این نوع ساختمان داده، فقط یک عنصر اول وجود دارد که دارای یک عنصر بعدی و فقط یک عنصر آخر وجود دارد که دارای یک عنصر قبلی است و همه عناصر دیگر این ساختمان داده‌ها در جاوا دارای یک عنصر قبلی و یک عنصر بعدی هستند. ب

خش بعدی مقاله به معرفی و بررسی ساختمان داده آرایه در جاوا اختصاص دارد.

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

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

ویژگی‌های ساختمان داده آرایه در جاوا در ادامه فهرست شده‌اند:

• آرایه‌ها دارای داده‌های ساده با نوع داده یکسان مانند عدد صحیح (Integer)، عدد اعشاری (Float) یا حتی نوع داده‌ای که کاربر تعریف کرده است (User Defined Data type) مانند ساختمان‌ها و اشیا هستند. همچنین، همه عناصر اندازه‌ای (Size) یکسان دارند.
• برخی از انواع داده رایج در آرایه‌ها به عنوان نوع داده‌ای پایه آن‌ها شناخته می‌شوند.
• معمولاً آرایه‌ها در جاوا به عنوان شی در نظر گرفته می‌شوند.
• اندیس‌های (Index) مقادیر آرایه‌ها با عدد صفر شروع می‌شوند.
• قبل از استفاده از آرایه‌ها باید آن‌ها را برای ذخیره داده‌ها تعریف کرد.
• محل ذخیره آرایه‌ها در جاوا به صورت تخصیص پویا (Dynamic Allocation) در ناحیه Heap است.
• عناصر آرایه در جاوا در مکان‌های حافظه به هم پیوسته (Contiguous Memory Location) ذخیره می‌شوند و تخصیص داده اولین عنصر از کوچک‌ترین مکان حافظه شروع می‌شود.
• عناصر آرایه در جاوا به صورت تصادفی (Randomly) قابل دسترسی هستند.
• ساختمان داده آرایه در جاوا به طور کامل پویا (Dynamic) نیست.
• طول آرایه‌ها در جاوا را می‌توان به وسیله متُد یا همان تابع «Length» پیدا کرد.
• سایز آرایه باید به صورت مقدار عدد صحیح باشد.

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

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

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

package org.arpit.java2blog;
 
import java.util.Arrays;
public class StringArrayMain {
 
    public static void main(String[] args) {
        String[] strArr = {"One","Two","Three"};
 
        System.out.println("Array elements are:");
        // تکرار روی آرایه
        for (int i=0;i

خروجی کدهای فوق به صورت زیر نشان داده شده است:

Array elements are:
One
Two
Three
====================
Printing array elements using Arrays.toString():
====================
[One, Two, Three]

• مقاله‌های پیشنهادی:
  • عملیات در آرایه: جستجو، درج و حذف — به زبان ساده
  • پیچیدگی زمانی عملیات جاوا روی انواع ساختمان داده — به زبان ساده
  • متغیر در برنامه نویسی چیست و چه کاربردی دارد؟ — Variable به زبان ساده

در بخش بعدی مقاله «ساختمان داده در جاوا» ساختمان داده لیست پیوندی مورد بررسی قرار می‌گیرد.

ساختمان داده لیست پیوندی در جاوا چیست؟

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

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

لیست تک پیوندی یا یک طرفه

لیست تک پیوندی یا یک طرفه یا تک جهتی (Singly Linked List | Uni Directional) همان‌طور که در تصویر زیر مشخص است، فقط به صورت رو به جلو و در یک جهت می‌تواند داده‌ها را دریافت کند.

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

در ادامه برای درک بهتر و آشنایی با لیست پیوندی، مثالی برای لیست پیوندی یک طرفه ارائه شده است:

package org.arpit.java2blog.datastructures;
 
class Node {
    public int data;
    public Node next;
 
    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}
 
public class MyLinkedList {
    private Node head;
 
    public boolean isEmpty() {
        return (head == null);
    }
 
    // متد درج گره در ابتدای لیست پیوندی
    public void insertFirst(int data) {
        Node newHead = new Node();
        newHead.data = data;
        newHead.next = head;
        head = newHead;
    }
 
    // متد حذف گره از ابتدای لیست پیوندی
    public Node deleteFirst() {
        Node temp = head;
        head = head.next;
        return temp;
    }
 
    // متد برای حذف گره ارائه شده در برنامه
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next = temp.next.next;
    }
 
    // متد برای درج در انتهای لیست پیوندی
    public void insertLast(int data) {
        Node current = head;
        while (current.next != null) {
            current = current.next; // تهی شود، حلقه ایجاد خواهد شد current.next تا زمانی که
        }
        Node newNode = new Node();
        newNode.data = data;
        current.next = newNode;
    }
 
    // متد برای چاپ لیست پیوندی
    public void printLinkedList() {
        System.out.println("Printing LinkedList (head --> last) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }
 
    public static void main(String args[])
    {
        MyLinkedList myLinkedlist = new MyLinkedList();
        myLinkedlist.insertFirst(50);
        myLinkedlist.insertFirst(60);
        myLinkedlist.insertFirst(70);
        myLinkedlist.insertFirst(10);
        myLinkedlist.insertLast(20);
        myLinkedlist.printLinkedList();
        // لیست پیوندی به صورت زیر خواهد بود:
        // 10 -> 70 ->  60 -> 50 -> 20
 
        System.out.println("=========================");
        System.out.println("Delete node after Node 60");
        Node node=new Node();
        node.data=60;
        myLinkedlist.deleteAfter(node);
        // پس از حذف گره بعد از ۱، لیست پیوندی به صورت زیر خواهد بود:
        // 10 -> 70 -> 60 -> 20
 
        System.out.println("=========================");
        myLinkedlist.printLinkedList();
    }
}

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

Printing LinkedList (head –> last)
{ 10 }
{ 70 }
{ 60 }
{ 50 }
{ 20 }
=========================
Delete node after Node 60
=========================
Printing LinkedList (head –> last)
{ 10 }
{ 70 }
{ 60 }
{ 20 }

لیست پیوندی دو طرفه

لیست پیوندی دو طرفه یا همان دو جهته (Doubly Linked List | Bi Directional) در دو جهت یعنی هم به صورت رو به جلو و هم به صورت رو به عقب می‌تواند داده‌ها را دریافت کند. دارای دو اشاره‌گر است که یکی از آن‌ها به گره قبلی و یکی از آن‌ها به گره بعدی اشاره می‌کنند.

این نوع لیست پیوندی پیمایش از دو طرف لیست را ممکن می‌سازد. تصویر زیر برای درک بهتر این نوع از ساختمان داده‌ها در جاوا ارائه شده است.

در ادامه مثالی برای لیست پیوندی دو طرفه ارائه شده است:

package org.arpit.java2blog.datastructures;
 
class Node {
    public int data;
    public Node next;
    public Node prev;
 
    public void displayNodeData() {
        System.out.println("{ " + data + " } ");
    }
}
 
public class MyDoublyLinkedList {
 
    private Node head;
    private Node tail;
    int size;
 
    public boolean isEmpty() {
        return (head == null);
    }
 
    // متد برای درج گره در ابتدای لیست پیوندی
    public void insertFirst(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = head;
        newNode.prev=null;
        if(head!=null)
            head.prev=newNode;
        head = newNode;
        if(tail==null)
            tail=newNode;
        size++;
    }
 
    // متد برای درج گره در انتهای لیست پیوندی
    public void insertLast(int data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.next = null;
        newNode.prev=tail;
        if(tail!=null)
            tail.next=newNode;
        tail = newNode;
        if(head==null)
            head=newNode;
        size++;
    }
    // متد حذف گره از ابتدای لیست پیوندی دو طرفه
    public Node deleteFirst() {
 
        if (size == 0)
            throw new RuntimeException("Doubly linked list is already empty");
        Node temp = head;
        head = head.next;
        head.prev = null;
        size--;
        return temp;
    }
 
    // متد حذف گره از انتهای لیست پیوندی دو طرفه
    public Node deleteLast() {
 
        Node temp = tail;
        tail = tail.prev;
        tail.next=null;
        size--;
        return temp;
    }
 
    // متد برای حذف گره پس از یک گره خاص
    public void deleteAfter(Node after) {
        Node temp = head;
        while (temp.next != null && temp.data != after.data) {
            temp = temp.next;
        }
        if (temp.next != null)
            temp.next.next.prev=temp;
        temp.next = temp.next.next;
 
    }
 
    // (Forward) متد چاپ لیست پیوندی دو طرفه رو به جلو 
    public void printLinkedListForward() {
        System.out.println("Printing Doubly LinkedList (head --> tail) ");
        Node current = head;
        while (current != null) {
            current.displayNodeData();
            current = current.next;
        }
        System.out.println();
    }
 
    // (Backward) متد چاپ لیست پیوندی دو طرفه رو به عقب
    public void printLinkedListBackward() {
        System.out.println("Printing Doubly LinkedList (tail --> head) ");
        Node current = tail;
        while (current != null) {
            current.displayNodeData();
            current = current.prev;
        }
        System.out.println();
    }
 
    public static void main(String args[])
    {
        MyDoublyLinkedList mdll = new MyDoublyLinkedList();
        mdll.insertFirst(50);
        mdll.insertFirst(60);
        mdll.insertFirst(70);
        mdll.insertFirst(10);
        mdll.insertLast(20);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
 
        System.out.println("================");
        // :لیست پیوندی دو طرفه به صورت زیر خواهد بود
        // 10 ->  70 -> 60 -> 50 -> 20
 
        Node node=new Node();
        node.data=10;
        mdll.deleteAfter(node);
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
        // :بعد از حذف نود پس از ۱، لیست پیوندی به صورت زیر خواهد شد
        // 20 -> 10 -> 60-> 50
        System.out.println("================");
        mdll.deleteFirst();
        mdll.deleteLast();
 
        // :پس از انجام عملیات فوق، لیست پیوندی به صورت زیر خواهد شد
        //  60 -> 50
        mdll.printLinkedListForward();
        mdll.printLinkedListBackward();
    }
}

خروجی مثال فوق که مثالی برای ساختمان داده لیست پیوندی دو طرفه در جاوا است به صورت زیر نمایش داده می‌شود:

Printing Doubly LinkedList (head –> tail)
{ 10 }
{ 70 }
{ 60 }
{ 50 }
{ 20 }

Printing Doubly LinkedList (tail –> head)
{ 20 }
{ 50 }
{ 60 }
{ 70 }
{ 10 }

================
Printing Doubly LinkedList (head –> tail)
{ 10 }
{ 60 }
{ 50 }
{ 20 }

Printing Doubly LinkedList (tail –> head)
{ 20 }
{ 50 }
{ 60 }
{ 10 }

================
Printing Doubly LinkedList (head –> tail)
{ 60 }
{ 50 }

Printing Doubly LinkedList (tail –> head)
{ 50 }
{ 60 }

لیست پیوندی حلقوی

در لیست پیوندی حلقوی یا دایره‌ای (Circular Linked List) گره‌ها می‌توانند به صورت دایره‌ای مانند شکل زیر باهم در ارتباط باشند. در این لیست پیوندی هیچ گره تهی وجود ندارد و هر گره‌ای را می‌توان به عنوان گره اول تعریف کرد.

لیست پیوندی‌های دو طرفه در پیاده‌سازی صف‌‌های دایره‌ای مؤثر هستند.

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

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

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

ساختمان داده پشته در جاوا چیست؟

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

در ادامه بخش ویژگی‌های پشته ارائه شده است:

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

مثال‌های عملی از ساختمان داده پشته در جاوا شامل معکوس کردن یک کلمه، بررسی صحت توالی پرانتزها، حل الگوریتم ماز (Maze) در جاوا، فراخوانی توابع تو در تو (Nested Function)، اجرای عملکرد برگشت در مرورگرها و سایر موارد هستند. کدهای زیر مثالی برای پیاده‌سازی پشته با استفاده از آرایه در جاوا است:

package org.arpit.java2blog.datastructures;
 
public class MyStack {
    int size;
    int arr[];
    int top;
 
    MyStack(int size) {
        this.size = size;
        this.arr = new int[size];
        this.top = -1;
    }
 
    public void push(int element) {
        if (!isFull()) {
            top++;
            arr[top] = element;
            System.out.println("Pushed element:" + element);
        } else {
            System.out.println("Stack is full !");
        }
    }
 
    public int pop() {
        if (!isEmpty()) {
            int topElement = top;
            top--;
            System.out.println("Popped element :" + arr[topElement]);
            return arr[topElement];
 
        } else {
            System.out.println("Stack is empty !");
            return -1;
        }
    }
 
    public int peek() {
        if(!this.isEmpty())
            return arr[top];
        else
        {
            System.out.println("Stack is Empty");
            return -1;
        }
    }
 
    public boolean isEmpty() {
        return (top == -1);
    }
 
    public boolean isFull() {
        return (size - 1 == top);
    }
 
    public static void main(String[] args) {
        MyStack myStack = new MyStack(5);
        myStack.pop();
        System.out.println("=================");
        myStack.push(100);
        myStack.push(90);
        myStack.push(10);
        myStack.push(50);
        System.out.println("=================");
        myStack.pop();
        myStack.pop();
        myStack.pop();
        System.out.println("=================");
    }
}

خروجی کدهای فوق به صورت زیر است:

Stack is empty !
=================
Pushed element:100
Pushed element:90
Pushed element:10
Pushed element:50
=================
Popped element :50
Popped element :10
Popped element :90
=================

در ادامه مثالی برای پیاده‌سازی پشته با استفاده از لیست پیوندی ارائه شده است:

package org.arpit.java2blog.datastructures;
 
public class StackUsingLinkedList {
    private Node head; // اولین گره
 
    // .کلاس بعدی برای تعریف گره در لیست پیوندی ارائه شده است
    private class Node {
        int value;
        Node next;
    }
 
    public StackUsingLinkedList() {
        head = null;
    }
 
    // .برای شبیه‌سازی پشته، مقدار از ابتدای لیست حذف می‌شود
    public int pop() throws LinkedListEmptyException {
        if (head == null) {
            throw new LinkedListEmptyException();
        }
        int value = head.value;
        head = head.next;
        return value;
    }
 
    // .برای شبیه‌سازی پشته، مقدار به ابتدای لیست اضافه می‌شود
    public void push(int value) {
        Node prevHead = head;
        head = new Node();
        head.value = value;
        head.next = prevHead;
    }
 
    public static void main(String args[])
    {
        StackUsingLinkedList sll=new StackUsingLinkedList();
        sll.push(200);
        sll.push(150);
        sll.push(80);
        sll.push(90);
        sll.push(600);
        sll.push(175);
        System.out.println("Removed element from LinkedList: "+sll.pop());
        System.out.println("Removed element from LinkedList: "+sll.pop());
        sll.push(100);
        System.out.println("Removed element from LinkedList: "+sll.pop());
        printList(sll.head);
    }
    public static void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
}
 
/**
 * .اگر لیست پیوندی خالی باشد از کلاس زیر استفاده می‌شود
 */
 
class LinkedListEmptyException extends RuntimeException {
    private static final long serialVersionUID = 1L;
 
    public LinkedListEmptyException() {
        super();
    }
 
    public LinkedListEmptyException(String message) {
        super(message);
    }
}

خروجی مثال فوق به صورت زیر است:

Removed element from LinkedList: 175
Removed element from LinkedList: 600
Removed element from LinkedList: 100
90 80 150 200

• مقاله‌های پیشنهادی:
  • پیاده سازی پشته با استفاده از صف — به زبان ساده
  • مرتب سازی پشته با الگوریتم بازگشتی — به زبان ساده

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

ساختمان داده صف در جاوا چیست؟

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

عناصر را با اولویت زمانی می‌توان در صف درج کرد، اما فقط عناصری را که بیشترین زمان در صف بودند را می‌توان حذف کرد. در این ساختمان داده، درج‌ها همیشه از «انتها» (Rear) و حذف‌ها همیشه از «ابتدا» (Front) صف انجام می‌شوند. بخشی از ویژگی‌های صف در ادامه ارائه شده است:

• ساختمان داده‌های صف در جاوا اغلب به عنوان لیست‌های «اولین ورودی، اولین خروجی» معرفی می‌شوند.
• دو متُد اساسی زیر در صف پشتیبانی می‌شوند:
  • (e)Enqueue: افزودن عنصری مانند e به انتهای صف
  • ()Dequeue: بازگرداندن اولین عنصر صف (عنصر جلوی صف) و حذف آن

در بخش بعدی مقاله «ساختمان داده در جاوا» به بررسی انواع گوناگون صف‌ها در جاوا پرداخته شده است.

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

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

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

• مقاله پیشنهادی: پشته (Stack)، صف (Queue) و تجزیه عبارت — ساختار داده و الگوریتم‌ ها

ساختمان داده صف حلقوی در جاوا چیست؟

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

ساختمان داده صف دو طرفه در جاوا چیست؟

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

در بخش بعدی برنامه‌هایی مورد بررسی قرار می‌گیرند که در پیاده‌سازی‌های خود از صف استفاده می‌کنند.

برنامه‌هایی که از ساختمان داده صف در جاوا استفاده می‌کنند: ساختمان داده صف در جاوا دارای کاربردهای بسیاری است و در برنامه‌های زیادی از آن‌ها استفاده می‌شود. در این بخش به بررسی برخی از برنامه‌هایی پرداخته شده است که از این ساختمان داده‌ها در جاوا استفاده می‌کنند.

• ساختمان داده صف در پرس و جوهای تلفنی، درخواست‌های رزرو، جریان ترافیک و سایر موارد استفاده می‌شود. برای مثال حتی ممکن است در تماس با تلفن پشتیبانی‌های گویا و پیش از پاسخگویی کارشناس جمله «لطفا صبر کنید، شما در صف هستید.» اعلام شود.
• صف برای دسترسی به برخی از منابع مانند صف چاپگر، صف دیسک و سایر موارد استفاده می‌شود.
• از صف برای جست و جوی سطح اول (Breadth First Searching | BFS) در ساختمان داده‌هایی خاص مانند درخت‌ها و گراف‌ها در جاوا استفاده می‌شود.
• این ساختمان داده در مدیریت زمان‌بندی فرآیندها در سیستم عامل‌های چند وظیفه‌ای (Multitasking Operating System) مانند الگوریتم‌های زمان‌بندی (Scheduling Algorithm) «خدمت به ترتیب ورود» (First Come First Serve)، الگوریتم زمان‌بندی نوبت گردشی (Round Robin) و سایر موارد استفاده می‌شود.
• ساختمان داده صف در انتقال داده‌ها بین دو فرآیند به صورت نامتقارن (Asynchronous) مورد استفاده قرار می‌گیرد
• صف در زمان‌بندی پردازنده CPU کاربرد دارد.
• ساختمان داده صف در زمان‌بندی دیسک استفاده می‌شود.

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

package org.arpit.java2blog.datastructures;
 
public class MyQueue {
 
    private int capacity;
    int queueArr[];
    int front;
    int rear;
    int currentSize = 0;
 
    public MyQueue(int size) {
        this.capacity = size;
        front = 0;
        rear = -1;
        queueArr = new int[this.capacity];
    }
 
    /**
     * متدی برای اضافه کردن عناصر به صف
     */
    public void enqueue(int data) {
        if (isFull()) {
            System.out.println("Queue is full!! Can not add more elements");
        } else {
            rear++;
            if (rear == capacity - 1) {
                rear = 0;
            }
            queueArr[rear] = data;
            currentSize++;
            System.out.println(data + " added to the queue");
        }
    }
 
    /**
     * .این متد عناصر را از ابتدای صف حذف می‌کند
     */
    public void dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty!! Can not dequeue element");
        } else {
            front++;
            if (front == capacity - 1) {
                System.out.println(queueArr[front - 1] + " removed from the queue");
                front = 0;
            } else {
                System.out.println(queueArr[front - 1] + " removed from the queue");
            }
            currentSize--;
        }
    }
 
    /**
     * .متدی که پر بودن صف را بررسی می‌کند
     */
    public boolean isFull() {
        if (currentSize == capacity) {
            return true;
        }
        return false;
    }
 
    /**
     * .متدی که خالی بودن صف را بررسی می‌کند
     */
    public boolean isEmpty() {
 
        if (currentSize == 0) {
            return true;
        }
        return false;
    }
 
    public static void main(String a[]) {
 
        MyQueue myQueue = new MyQueue(6);
        myQueue.enqueue(1);
        myQueue.dequeue();
        myQueue.enqueue(30);
        myQueue.enqueue(44);
        myQueue.enqueue(32);
        myQueue.dequeue();
        myQueue.enqueue(98);
        myQueue.dequeue();
        myQueue.enqueue(70);
        myQueue.enqueue(22);
        myQueue.dequeue();
        myQueue.enqueue(67);
        myQueue.enqueue(23);
    }
}

خروجی مثال فوق که پیاده‌سازی صف با استفاده از آرایه در جاوا را نشان می‌دهد، به صورت زیر است:

1 added to the queue
1 removed from the queue
30 added to the queue
44 added to the queue
32 added to the queue
30 removed from the queue
98 added to the queue
44 removed from the queue
70 added to the queue
22 added to the queue
32 removed from the queue
67 added to the queue
23 added to the queue

مثال بعدی ارائه شده، پیاده‌سازی برنامه به وسیله ساختمان داده صف و با استفاده از لیست پیوندی را نشان می‌دهد:

package org.arpit.java2blog.datastructures;
 
public class QueueUsingLinkedList
{
    private Node front, rear;
    private int currentSize; // اندازه
 
    // ساختمان داده گره
    private class Node
    {
        int data;
        Node next;
    }
 
    // سازنده
    public QueueUsingLinkedList()
    {
        front = null;
        rear = null;
        currentSize = 0;
    }
 
    public boolean isEmpty()
    {
        return (currentSize == 0);
    }
 
    // .برای شبیه‌سازی صف، موردی از ابتدای لیست حذف می‌شود 
    public int dequeue()
    {
        int data = front.data;
        front = front.next;
        if (isEmpty())
        {
            rear = null;
        }
        currentSize--;
        System.out.println(data+ " removed from the queue");
        return data;
    }
 
    // .برای شبیه‌سازی صف داده‌ای به انتهای صف اضافه می‌شود
    public void enqueue(int data)
    {
        Node oldRear = rear;
        rear = new Node();
        rear.data = data;
        rear.next = null;
        if (isEmpty())
        {
            front = rear;
        }
        else
        {
            oldRear.next = rear;
        }
        currentSize++;
        System.out.println(data+ " added to the queue");
    }
    public static void main(String a[]){
 
        QueueUsingLinkedList queueUsingLinkedList = new QueueUsingLinkedList();
        queueUsingLinkedList.enqueue(60);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(10);
        queueUsingLinkedList.enqueue(20);
        queueUsingLinkedList.enqueue(40);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(70);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(80);
        queueUsingLinkedList.enqueue(100);
        queueUsingLinkedList.dequeue();
        queueUsingLinkedList.enqueue(150);
        queueUsingLinkedList.enqueue(50);
    }
}

خروجی برنامه فوق که مثالی برای پیاده‌سازی برنامه به وسیله ساختمان داده صف با لیست پیوندی است، به صورت زیر نمایش داده می‌شود:

60 added to the queue
60 removed from the queue
10 added to the queue
20 added to the queue
40 added to the queue
10 removed from the queue
70 added to the queue
20 removed from the queue
80 added to the queue
100 added to the queue
40 removed from the queue
150 added to the queue
50 added to the queue

بخش بعدی مقاله «ساختمان داده در جاوا» به بررسی ساختمان داده‌های غیر خطی و سلسله مراتبی در جاوا اختصاص داده شده است.

ساختمان داده غیر خطی در جاوا چیست؟

ساختمان داده غیر خطی یا سلسله مراتبی در جاوا، برای حذف و درج عناصر دارای ترتیب خاصی به صورت خطی ندارد. ساختمان داده‌های غیر خطی، ساختمان داده‌هایی چند سطحی (Multilevel Data Structure) به حساب می‌آیند.

در این بخش به بررسی برخی از مهم‌ترین این نوع ساختمان داده‌ها در جاوا پرداخته می‌شود. ابتدا در بخش بعدی ساختمان داده درخت دودویی در جاوا مورد بررسی قرار می‌گیرد.

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

درخت دودویی یا همان باینری (Binary Tree) یک ساختمان داده درختی غیر خطی و سلسله مراتبی است که هر گره آن دارای حداکثر دو فرزند است که با نام‌های فرزند سمت چپ (Left Child) و فرزند سمت راست (Right Child) شناخته می‌شوند.

هر درخت باینری دودویی دارای گروهی از گره‌ها به صورت زیر است:

• گره ریشه (Root Node): این ریشه بالاترین ریشه درخت است و گاهی به عنوان ریشه اصلی نیز شناخته می‌شود زیرا همه ریشه‌های دیگر از این ریشه نشأت می‌گیرند و به آن متصل هستند.
• زیر درخت سمت چپ (Left Sub Tree): یک درخت باینری است که در سمت چپ درخت باینری اصلی ایجاد می‌شود.
• زیر درخت سمت راست (Right Sub Tree): زیر درخت سمت راست نیز خودش یک درخت باینری به حساب می‌آید.

در ادامه این بخش، ویژگی‌های ساختمان داده درخت باینری در جاوا ارائه شده است:

• درخت باینری با دو روش به صورت زیر پیمایش می‌شود:
  • الگوریتم پیمایش عمق اول (Depth First Traversal): این نوع پیمایش شامل پیمایش «In Order» یا همان میان‌وندی به صورت «راست – ریشه – چپ»، پیمایش «Pre Order» یا همان پیش‌وندی به صورت «راست – چپ – ریشه» و پیمایش پس‌وندی یا همان «Post Order» به صورت «ریشه – راست – چپ» است.
  • الگوریتم پیمایش سطح اول (Breadth First Traversal): در این نوع از الگوریتم‌ها پیمایش به ترتیب سطح انجام می‌شود. (Level Order Traversal)
• پیچیدگی زمانی (Time Complexity) پیمایش درخت «(n)O» است.
• حداکثر تعداد گره‌ها در هر سطح $$l=2^{l-1}$$ است.

کاربردهای ساختمان داده درخت دودویی در جاوا چه هستند؟

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

• ساختمان داده درخت دودویی در بسیاری از برنامه‌های جست و جویی استفاده می‌شود که داده‌ها همواره در حال ورود و خروج هستند.
• درخت دودویی به عنوان یک جریان کار در ترکیب تصاویر دیجیتال برای جلوه‌های بصری (Visual Effect) مورد استفاده قرار می‌گیرد.
• می‌توان گفت تقریباً از درخت دودویی جاوا در هر مسیریاب (Router) با پهنای باند بالا (High Bandwidth) برای ذخیره جدول‌های مسیریاب استفاده می‌شود.
• این ساختمان داده در شبکه‌های بی‌سیم (Wireless Network) و تخصیص حافظه (Memory Allocation) استفاده می‌شود.
• در الگوریتم‌های فشرده‌سازی (Compression Algorithm) و بسیاری از الگوریتم‌های دیگر نیز استفاده می‌شود.

در ادامه مثالی برای درک بهتر ساختمان داده درخت دودویی یا باینری ارائه شده است:

package org.arpit.java2blog.datastructures;
 
import java.util.Stack;
 
public class BinaryTree {
 
    public static class Node
    {
        int data;
        Node left;
        Node right;
        Node(int data)
        {
            this.data=data;
        }
    }
 
    // راه حل بازگشتی
    public void preorder(Node root) {
        if(root !=  null) {
            //Pre order traversal
            System.out.printf("%d ",root.data);
            preorder(root.left);
            preorder(root.right);
        }
    }
 
    // راه حل تکراری
    public void preorderIter(Node root) {
 
        if(root == null)
            return;
 
        Stack s = new Stack();
        s.push(root);
 
        while(!s.empty()){
 
            Node n = s.pop();
            System.out.printf("%s ",n.data);
 
            if(n.right != null){
                s.push(n.right);
            }
            if(n.left != null){
                s.push(n.left);
            }
 
        }
 
    }
 
    public static void main(String[] args)
    {
        BinaryTree bi=new BinaryTree();
        // ایجاد ساختمان داده درخت باینری
        Node rootNode=createBinaryTree();
        System.out.println("Using Recursive solution:");
 
        bi.preorder(rootNode);
 
        System.out.println();
        System.out.println("-------------------------");
        System.out.println("Using Iterative solution:");
 
        bi.preorderIter(rootNode);
    }
 
    public static Node createBinaryTree()
    {
 
        Node rootNode =new Node(30);
        Node node20=new Node(50);
        Node node10=new Node(60);
        Node node30=new Node(80);
        Node node60=new Node(90);
        Node node50=new Node(100);
        Node node70=new Node(110);
 
        rootNode.left=node20;
        rootNode.right=node60;
 
        node20.left=node10;
        node20.right=node30;
 
        node60.left=node50;
        node60.right=node70;
 
        return rootNode;
    }
}

خروجی مثال درخت باینری ارائه شده به صورت زیر نمایش داده می‌شود:

Using Recursive solution:
30 50 60 80 90 100 110
————————-
Using Iterative solution:
30 50 60 80 90 100 110

در بخش بعدی مقاله «ساختمان داده در جاوا» به بررسی ساختمان داده درخت جست و جوی دودویی پرداخته شده است.

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

ساختمان داده درخت جست و جوی دودویی یا باینری (Binary Search Tree | BST) یک نوع خاصی از ساختمان داده درخت دودویی در جاوا به حساب می‌آید که دارای ویژگی‌های زیر است:

• در درخت جست و جوی دودویی گره‌هایی که کوچک‌تر از ریشه هستند در زیر درخت سمت چپ قرار می‌گیرند.
• در این ساختمان داده در جاوا گره‌هایی که بزرگ‌تر از ریشه هستند در زیر درخت سمت راست قرار می‌گیرند.
• درخت جست و جوی دودویی نباید گره تکراری داشته باشد.
• زیر درخت‌های چپ و راست هر دو باید به تنهایی یک درخت جست و جوی دودویی باشند.

در ادامه این بخش برای درک بهتر ساختمان داده درخت جستجوی باینری در جاوا مثالی برای آن ارائه شده است: (شکل این مثال با مثال بخش درخت دودویی تفاوتی ندارد.)

package org.arpit.java2blog.datastructures;
 
public class MyBinarySearchTree {
    public static class Node
    {
        int data;
        Node left;
        Node right;
        Node(int data)
        {
            this.data=data;
        }
    }
 
    public static boolean search(Node root, Node nodeToBeSearched)
    {
        if(root==null)
            return false;
        if(root.data== nodeToBeSearched.data)
        {
            return true;
        }
        boolean result=false;
 
        if(root.data > nodeToBeSearched.data)
            result=search(root.left,nodeToBeSearched);
        else if(root.data  nodeToBeInserted.data)
    {
        if(root.left==null)
            root.left=nodeToBeInserted;
        else
            insert(root.left,nodeToBeInserted);
    }
    else if(root.data 

خروجی مثال فوق به صورت زیر است:

Searching for node 55 : true
—————————
Inorder traversal of binary tree after adding 13:
5 10 13 20 30 40 50 55 60 70

در بخش بعدی این مقاله به بررسی و معرفی ساختمان داده درخت پیشوندی پرداخته شده است.

ساختمان داده درخت پیشوندی در جاوا چیست؟

ساختمان داده درخت پیشوندی (Trie Tree)، ساختمان داده‌ای است که به گونه‌ای داده‌ها را ذخیره‌سازی می‌کند تا بتوان آن‌ها را به راحتی بازیابی کرد. برای مثال این ساختمان داده برای پیاده‌سازی «Dictionary» مورد استفاده قرار می‌گیرد. در ادامه مثالی در رابطه با پیاده‌سازی ساختمان داده درخت پیشوندی مشاهده می‌شود.

در این مثال کلمات در درخت پیشوندی قرار گرفته‌اند. فرض می‌شود که قرار است کلمات do ،deal ،dear ،he ،hen ،heat و سایر موارد وارد شوند.

package org.arpit.java2blog.datastructures;
 
/*
 *  برنامه جاوا برای پیاده‌سازی درخت ترای
 */
 
import java.util.*;
 
class TrieNode
{
    char data;
    boolean isEnd;
    int count;
    LinkedList childList;
 
    /* سازنده */
    public TrieNode(char c)
    {
        childList = new LinkedList();
        isEnd = false;
        data = c;
        count = 0;
    }
    public TrieNode getChild(char c)
    {
        if (childList != null)
            for (TrieNode eachChild : childList)
                if (eachChild.data == c)
                    return eachChild;
        return null;
    }
}
 
public class Trie
{
    private TrieNode root;
 
    /* سازنده */
    public Trie()
    {
        root = new TrieNode(' ');
    }
    /* متد درج ترای از درخت ترای*/
    public void insert(String word)
    {
        if (search(word) == true)
            return;
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray() )
        {
            TrieNode child = tempCurr.getChild(ch);
            if (child != null)
                tempCurr = child;
            else
            {
                // .اگر فرزند وجود نداشت به لیست اضافه می‌شود
                tempCurr.childList.add(new TrieNode(ch));
                tempCurr = tempCurr.getChild(ch);
            }
            tempCurr.count++;
        }
        tempCurr.isEnd = true;
    }
    /* متد برای جست‌و‌جوی کلمات در درخت ترای*/
    public boolean search(String word)
    {
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray() )
        {
            if (tempCurr.getChild(ch) == null)
                return false;
            else
                tempCurr = tempCurr.getChild(ch);
        }
        if (tempCurr.isEnd == true)
            return true;
        return false;
    }
    /* متد برای حذف کلمات از درخت ترای*/
    public void remove(String word)
    {
        if (search(word) == false)
        {
            System.out.println(word +" does not present in trien");
            return;
        }
        TrieNode tempCurr = root;
        for (char ch : word.toCharArray())
        {
            TrieNode child = tempCurr.getChild(ch);
            if (child.count == 1)
            {
                tempCurr.childList.remove(child);
                return;
            }
            else
            {
                child.count--;
                tempCurr = child;
            }
        }
        tempCurr.isEnd = false;
    }
 
    public static void displayWordsInTrie(TrieNode root, String str)
    {
        TrieNode tempCurr = root;
        if(root.childList==null || root.childList.size()==0)
            return;
        Iterator iter=tempCurr.childList.iterator();
        while(iter.hasNext())
        {
            TrieNode trieNode= (TrieNode) iter.next();
            str+=trieNode.data;
            displayWordsInTrie(trieNode,str);
            if(trieNode.isEnd==true)
            {
                System.out.print(" "+str);
                str=str.substring(0,str.length()-1);
            }
            else
            {
                str=str.substring(0,str.length()-1);
            }
        }
 
    }
    public static void main(String[] args)
    {
        Trie t = new Trie();
        t.insert("apple");
        t.insert("ape");
        t.insert("goat");
        t.insert("goa");
        t.insert("apt");
 
        System.out.println("go present in trie : "+t.search("go"));
        System.out.println("goa present in trie : "+t.search("goa"));
        System.out.println("appl present in trie : "+t.search("ape"));
        System.out.println("========================");
        System.out.println("Displaying all word present in trie : ");
        displayWordsInTrie(t.root,"");
    }
}

خروجی مثال پیاده‌سازی ساختمان داده درخت پیشوندی فوق به صورت زیر نشان داده می‌شود:

go present in trie : false
goa present in trie : true
appl present in trie : true
========================
Displaying all word present in trie :
apple ape apt goat goa

بخش بعدی این مقاله به شرح ساختمان داده هرمی دودویی در جاوا اختصاص دارد.

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

هرمی دودویی یا همان باینری (Binary Heap) یک درخت دودویی کامل است که ویژگی‌های هرمی را پاسخ می‌دهد.

به عبارت دیگر، نوع متفاوتی از درخت باینری با ویژگی‌های زیر است:

• هرمی یک درخت باینری کامل است. به درختی کامل گفته می‌شود که همه سطوح آن کامل باشند، فقط گاهی امکان دارد که عمیق‌ترین سطح آن کامل نباشد. ویژگی‌های درخت باینری هرمی آن را برای ذخیره در یک آرایه مناسب می‌کند.
• باینری هرمی به صورت هرمی مینیمم (Min Heap) و هرمی ماکسیمم (Max Heap) دارای ویژگی‌های زیر است:
  • هرمی دودویی مینیمم: برای هر گره‌ای در این هرمی، مقادیر گره‌ها کم‌تر و مساوی مقادیر گره‌های فرزندان است.
  • هرمی دودویی ماکسیمم: برای هر گره‌ای در این نوع از هرمی‌ها، مقادیر هر گره بزرگ‌تر و مساوی مقادیر فرزندان آن است.

برنامه‌های محبوب هرمی دودویی شامل پیاده‌سازی مؤثر و کارآمد صف‌های اولویت (Priority Queue)، پیدا کردن کوچک‌ترین یا بزرگ‌ترین عنصر در آرایه‌ها با بهترین کیفیت و سایر موارد می‌شوند. در ادامه برای درک بهتر موضوع ساختمان داده هرمی در جاوا مثالی برای هرمی مینیمم ارائه شده است:

package org.arpit.java2blog.datastructures;
 
import java.util.Arrays;
public class MinHeap
{
    int Heap[];
    int size;
    int capacity;
 
    public MinHeap(int size)
    {
        this.capacity = size;
        this.size = 0;
        Heap = new int[size];
    }
 
    int parent(int i)
    {
        return (i - 1)/2;     // .ام را برمی‌گرداند i اندیس گره والد
    }
 
    int leftChild(int i)
    {
        return (2 * i) + 1;              // .اندیس فرزند سمت چپ را برمی‌گرداند
    }
 
    int rightChild(int i)
    {
        return (2 * i) + 2;              // .اندیس فرزند سمت راست را برمی‌گرداند
    }
 
    boolean isLeaf(int i)   // امین گره، گره برگ است یا خیر i بررسی می‌کند که آیا
    {
        if (rightChild(i) >= size || leftChild(i) >= size)
            return true;
 
        return false;
    }
 
    /* متد درج گره در ساختمان داده مین هیپ در جاوا
 
     */
    void insert(int data)
    {
        if (size >= capacity)
            return;
 
        Heap[size] = data;
        int tempCurr = size;
 
        while (Heap[tempCurr]  Heap[leftChild(i)] || Heap[i] > Heap[rightChild(i)])
            {
                if(Heap[leftChild(i)] = 0; i--)
        {
            minHeapify(i);
        }
    }
 
    // چاپ محتوای هیپ
    public void printHeap()
    {
        for (int i = 0; i 

خروجی مثال ساختمان داده مین هرمی فوق به صورت زیر است:

The Min Heap is : [100, 200, 500, 700, 800, 900]
The Min Value in the heap : 100

Root : 100 Left : 200 Right : 500
Parent : 200 Left : 700 Right : 800
Parent : 500 Left : 900

The Min Heap after Removing node is :200 700 500 900 800
Extracted Minimum Node in the heap : 100

Root : 200 Left : 700 Right : 500
Parent : 700 Left : 900 Right : 800

در بخش بعدی مقاله «ساختمان داده در جاوا» به بررسی ساختمان داده گراف در جاوا پرداخته شده است.

ساختمان داده گراف در جاوا چیست؟

گراف یک ساختمان داده غیر خطی در جاوا است و مؤلفه‌هایی که در ادامه ارائه شده‌اند، آن را تعریف می‌کنند:

• گراف شامل مجموعه‌ای از تعداد محدودی از رئوس (Vertice) است که به عنوان گره یا همان «Node» شناخته می‌شوند.
• ساختمان داده گراف دارای یالی (Edge) با مجموعه محدودی از جفت‌های مرتب به شکل (e, v) است.
• V نشان دهنده تعداد رئوس است.
• E نشان دهنده تعداد یال‌ها است.

در بخش بعدی مقاله به بررسی انواع گراف‌ها و طبقه‌بندی انواع آن‌ها پرداخته شده است.

انواع طبقه‌بندی‌های ساختمان داده گراف در جاوا چگونه است؟

ساختمان داده گراف در جاوا بر اساس پارامترهای آن به دو دسته «گراف مسیر» (Direction Graph) و «گراف وزن» (Weight Graph) طبقه‌بندی می‌شود که در این بخش به بررسی هر کدام از آن‌ها پرداخته می‌شود. ابتدا ساختمان داده گراف مسیر مورد بررسی قرار می‌گیرد.

ساختمان داده گراف مسیر در جاوا چیست؟

در ساختمان داده گراف مسیر در جاوا، گراف‌ها به دو دسته گراف جهت‌دار (Directed Graph) و گراف بدون جهت (Undirected Graph) تقسیم می‌شوند. در بخش بعدی این مقاله، گراف جهت‌دار بررسی شده است.

گراف جهت‌دار در جاوا چیست؟

گراف جهت‌دار مجموعه‌ای از گره‌ها یا رئوس متصل به یکدیگر است که در آن همه یال‌ها دارای جهتی از یک رأس به رأس دیگر هستند. تصویر زیر نمونه ساده‌ای از این نوع گراف به حساب می‌آید.

• مقاله پیشنهادی: برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی

حال در این بخش برای درک بهتر گراف در جاوا و آشنایی با کدهای برنامه نویسی گراف در طراحی گراف‌ها مثالی از یک گراف جهت‌دار با استفاده از الگوریتم پیمایش جست و جوی عمق اول (Depth First Search | DFS) ارائه شده است:

package org.arpit.java2blog.datastructures;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
 
public class GraphMain
{
 
    static class Node
    {
        int data;
        boolean visited;
        List neighbours;
 
        Node(int data)
        {
            this.data=data;
            this.neighbours=new ArrayList();
 
        }
        public void addneighbours(Node neighbourNode)
        {
            this.neighbours.add(neighbourNode);
        }
        public List getNeighbours() {
            return neighbours;
        }
        public void setNeighbours(List neighbours) {
            this.neighbours = neighbours;
        }
    }
 
    // الگوریتم پیمایش عمق اول بازگشتی
    public  void recursiveDFS(Node node)
    {
        System.out.print(node.data + " ");
        List neighbours=node.getNeighbours();
        node.visited=true;
        for (int i = 0; i  stack=new  Stack();
        stack.add(node);
        while (!stack.isEmpty())
        {
            Node element=stack.pop();
            if(!element.visited)
            {
                System.out.print(element.data + " ");
                element.visited=true;
            }
 
            List neighbours=element.getNeighbours();
            for (int i = 0; i 

خروجی مثال فوق به صورت زیر است:

Iterative DFS traversal
40 20 50 70 60 30 10
Recursive DFS traversal
40 10 30 60 70 20 50

در بخش بعدی مقاله «ساختمان داده در جاوا» به معرفی گراف بدون جهت پرداخته شده است.

گراف بدون جهت در جاوا چیست؟

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

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

بر پایه وزن‌ها، گراف می‌تواند به دو دسته گراف وزن‌دار (Weighted Graph) و گراف بدون وزن (Unweighted Graph) تقسیم شود. در ادامه این بخش به بررسی دو نوع گراف مذکور پرداخته می‌شود. ابتدا بخش بعدی به معرفی گراف وزن‌دار اختصاص داده شده است.

گراف وزن‌دار در جاوا چیست؟

ساختمان داده گراف وزن‌دار در جاوا، گرافی است که هر یال آن دارای وزن باشد. این گراف نوع خاصی از گراف برچسب‌دار (Labeled Graph) به حساب می‌آید. در تصویر زیر نمونه‌ای از یک گراف وزن‌دار مشاهده می‌شود. در بخش بعدی این مقاله، گراف بدون وزن شرح داده شده است.

گراف بدون وزن در جاوا چیست؟

در ساختمان داده گراف بدون وزن هیچ وزنی برای یال‌های آن اختصاص داده نشده است. در تصویر زیر یک گراف بدون وزن ساده نشان داده شده است.

بخش بعدی این مقاله به معرفی ساختمان داده مجموعه اختصاص دارد.

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

مجموعه (Set) ساختمان داده‌ای خاص است که از مقادیر تکراری (Duplicate Value) استفاده نمی‌کند. این ساختمان داده در جاوا معمولاً برای ذخیره عناصر منحصربه‌فرد مانند شناسه کاربری یکتا (ID) مورد استفاده قرار می‌گیرد.

پیاده‌سازی‌های زیادی از ساختمان داده مجموعه در جاوا وجود دارند که برخی از آن‌ها شامل مجموعه درهم‌سازی پیوندی (Linked Hash Set)، مجموعه درهم‌سازی (Hash Set) و مجموعه درخت (Tree Set) می‌شوند که این ساختمان داده‌ها در جاوا توسط مجموعه API جاوا (Java Collection API) ارائه شده‌اند. در تصویر زیر نمونه‌ای از ساختمان داده مجموعه در جاوا مشاهده می‌شود.

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

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

فرض می‌شود که شئی وجود دارد و کلیدی به آن اختصاص داده می‌شود تا جست و جو را آسان کند. برای ذخیره کلید و مقدار به صورت جفت، می‌توان از یک آرایه ساده مانند یک ساختمان داده در جاوا استفاده کرد که در آن کلیدها (اعداد صحیح) می‌توانند مستقیماً به عنوان اندیسی برای ذخیره مقادیر داده‌ها استفاده شوند. با این حال، در مواردی که کلید بسیار بزرگ است و به عنوان یک اندیس به طور مستقیم نمی‌توان از آن استفاده کرد از روش جدول درهم‌سازی (Hash Table) استفاده می‌شود.

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

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

• آرایه سطلی (Bucket Array): آرایه سطلی برای تابع درهم‌سازی یک آرایه A با سایز N، آرایه‌ای است که هر سلول آن یک سطل یا «Bucket» نامیده می‌شود. این آرایه مجموعه‌ای از جفت‌های کلید و مقادیر است. عدد صحیح N ظرفیت آرایه A را مشخص می‌کند.
• تابع درهم‌سازی: هر تابعی که کلید k را به عدد صحیحی در بازه [N-1 و 0] نگاشت کند، تابع درهم‌سازی نامیده می‌شود. N در این بازه ظرفیت آرایه سطلی را نشان می‌دهد.

زمانی که اشیا در جدول‌های درهم‌سازی قرار می‌گیرند، امکان دارد که اشیا گوناگون دارای کد درهم‌سازی یکسانی باشند. به این مسئله تصادم یا برخورد (Collision) گفته می‌شود. برای جلوگیری از تصادم، روش‌هایی مانند آدرس‌دهی زنجیره‌ای (Chain) یا باز (Open) وجود دارند.

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

جمع‌بندی

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

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