ساختمان داده لیست پیوندی Linked List در جاوا

لیست پیوندی نوعی از ساختمان داده برای حافظه است و ذخیره ی داده ها است. اما لیست پیوندی بر خلاف آرایه و … محدودیت مکانی ندارد و هر تعداد داده ای می‌توان در آن قرار داد. لیست پیوندی در اصل از یک گره یا Node به اسم head تشکیل شده است که همان گره خود اشاره گری به یک گره ی دیگر در خود دارد و آن گره هم یک اشاره گر به گره ی دیگر و … و عملا ما لیست یا زنجیری از گره ها را خواهیم داشت که به آن لیست پیوندی می‌گویند 🙂
معمولا برای لیست پیوندی متدهای زیر ممکن است تعریف شود:
متد insertFirst: یک داده به ابتدای لیست اضافه می‌کند.
متد insertLast: یک داده به انتهای لیست اضافه می‌کند.
متد deleteFirst: داده‌ی ابتدای لیست را برمی‌گرداند و سپس آن گره را از لیست حذف می‌کند.
متد deleteLast: داده‌ی انتهای لیست را برمی‌گرداند و سپس آن گره را از لیست حذف می‌کند.
متد peekFirst: داده‌ی ابتدای لیست را برمی‌گرداند ولی آن گره را از لیست حذف نمی‌کند.
متد peekLast: داده‌ی انتهای لیست را برمی‌گرداند ولی آن گره را از لیست حذف نمی‌کند.
متد isEmpty: در صورتی که لیست خالی باشد مقدار true را برمی‌گرداند.

Node.java

/*
 Node
 v1: 21 Nov 2015
 v2: 25 Nov 2015
 v3: 05 Dec 2015
 Java Language
 By: Sina Moradi
 http://Samiantec.ir
 */

package src;

class Node {

	int data;
	Node next;

	Node() {
		this.data = 0;
		this.next = null;
	}

	Node(int data, Node next) {
		this.data = data;
		this.next = next;
	}

	Node(Node other) {
		this.data = other.data;
		this.next = other.next;
	}

}

LinkedList.java

/*
 Linked List
 v1: 21 Nov 2015
 v2: 25 Nov 2015
 v3: 05 Dec 2015
 Java Language
 By: Sina Moradi
 http://Samiantec.ir
 */

package src;

public class LinkedList {

	private Node head,tail;

	public LinkedList() {
		head = null;
		tail = null;
	}

	public Node getHead() {
		return new Node(head);
	}

	public void insertFirst(int data) {
		head = new Node(data, head);
		if (tail == null)
			tail = head;
	}

	public void insertLast(int data) {
		Node newNode=new Node(data, null);
		if (tail == null) {
			tail = newNode;
			head = newNode;
		}
		else {
			tail.next = newNode;
			tail = newNode;
		}
	}

	public int popFirst() {
		if (isEmpty()) {
			System.out.print("List is empty");
			System.exit(0);
		}
		int t=head.data;
		head = head.next;
		return t;
	}

	public int popLast() {
		if (isEmpty()) {
			System.out.print("List is empty");
			System.exit(0);
		}
		int t=tail.data;
		Node s=head;
		while (s.next != null && s.next != tail)
			s = s.next;
		tail = s;
		if (tail == head) {
			head = null;
			tail = null;
		}
		else
			tail.next = null;
		return t;
	}

	public int peekFirst() {
		if (isEmpty()) {
			System.out.print("List is empty");
			System.exit(0);
		}
		return head.data;
	}

	public int peekLast() {
		if (isEmpty()) {
			System.out.print("List is empty");
			System.exit(0);
		}
		return tail.data;
	}

	public boolean isEmpty() {
		return head == null;
	}

	public void print() {
		Node t=head;
		System.out.println();
		while (t != null) {
			System.out.print(t.data);
			t = t.next;
		}
	}

}

Test.java

/*
 Test
 v1: 21 Nov 2015
 v2: 25 Nov 2015
 v3: 05 Dec 2015
 Java Language
 By: Sina Moradi
 http://Samiantec.ir
 */

import src.*;

public class Test {

	public static void main(String[] args) {
		LinkedList a=new LinkedList();
		a.insertLast(2);
		a.insertLast(3);
		a.insertLast(5);
		a.popLast();
		a.insertLast(7);
		a.popFirst();
		a.insertFirst(0);
		a.print();
		//a.insertFirst(5);
		//a.popLast();
		//System.out.println(a.isEmpty());
		//System.out.println(a.peekFirst());
	}

}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

14 − 9 =