תכנות מתקדם ב-Java/מבני נתונים

חלק חיוני מתכנון של תוכנית הוא ארגון המידע, ופעמים רבות הכלים הבסיסיים - המשתנים הפשוטים והמערכים - אינם מספיקים לצרכינו. לשם כך, פותחו דרכים וצורות מתוחכמות יותר לאגירה ושליפה של נתונים, אשר מתאימות לצרכים שונים. בפרק זה נראה כמה סוגים של מבנים, משוכללים מעט יותר מהמערך המוכר. לא נעסוק כאן, לעת עתה, בפרטים של סיבוכיות או יעילות מופשטת.

מבנה נתונים בגודל משתנה

בעייה בסיסית שעומדת מולנו לעיתים קרובות נובעת מכך שגודל המידע שאנו צריכים להחזיק אינו תמיד אחיד. ניקח כדוגמה את התוכנית המוכרת לניהול מלאי. מצד אחד, אם נוסיף מוצרים רבים למלאי - המקום יגמר עד מהרה. מצד שני, אם נגדיר מלכתחילה את גודל המלאי להיות גדול מאוד - קרוב לודאי שנבזבז זיכרון רב לשווא. אם, למשל, נגדיר מלאי כך שיוכל להחזיק 1000 מוצרים, אך נכניס רק 10 - יצא שהשתמשנו בזיכרון רב מאוד, בו לא היה שום צורך. יש כמה גישות לפתרון בעייה זו, כל אחת בעלת חסרונות ויתרונות משלה. כמו ההבדל בין רשימה למערך...

וקטור - מערך בגודל משתנה

הגישה הראשונה שנציג מבוססת על מערך, בעל תכונה מיוחדת: הוא יכול להתרחב בהתאם לצרכינו. כמו מערך רגיל, הוא יאפשר הכנסה של נתונים לתא מבוקש, ושליפה שלהם לפי מספר התא.

הסבר

וקטור הוא מבנה פשוט אך שימושי להפליא. הוא מתבסס על מערך פנימי, אותו ניתן להגדיל כרצוננו. המחלקה שלנו למעשה "תעטוף" את המערך הפנימי, כך שאם תתבצע גישה למקום שעדיין לא אותחל - ניתן יהיה לטפל בכך כרצוננו. פרט לכך, ההתנהגות דומה מאוד לזו של מערך רגיל. הוקטור שנראה תומך רק בהכנסה והוצאה. נעיר כי מימושים קיימים (כמו, למשל, זה שמציעה Java) מכילים הרבה אפשרויות נוספות.

מימוש

כדי לממש את הוקטור, נבנה מחלקה בשם MyVector. המחלקה תכיל שני שדות פנימיים: מערך, שיכיל את המידע, ומשתנה נוסף שיכיל את גודל המערך הנוכחי. הוקטור שלנו יתמוך רק בפעולות הבסיסיות בהן תומך המערך, ולא יהיה סלחני יותר ממערך רגיל: אם משתמש ינסה להכניס או לגשת לתוכן תא לא חוקי - התוכנית תדפיס הודעה ותעצור. ההבדל היחיד הוא שאם משתמש ינסה לכתוב לתוכן תא שמספרו חורג מגודל המערך - התוכנית תגדיל את המערך בהתאם ותכתוב למקום הרצוי.

שדות ובנאים

בשלב הראשון, נגדיר שני שדות אליהם נזדקק: השדה הראשון (והחשוב ביותר) הוא המערך שיחזיק את המידע. השדה השני הוא משתנה שיכיל את גודל המערך.

// Array holding all data elements
private int _arr[];
// Current size of vector
private int _size;

כעת נגדיר בנאי מתאים. הבנאי יקבל ארגומנט יחיד שקובע מהו גודלו ההתחלתי של המערך הפנימי. במקרה והארגומנט הוא שלילי, השיטה reportError (שאת הקוד שלה ניתן לראות בתוכנית המלאה בהמשך) מדפיסה הודעת שגיאה ועוצרת את ריצת התוכנית.

/**
 * Constructor
 * @param size Initial size of vector
 */
public MyVector(int size) {
	if(size < 0) {
		reportError("Illegal size");
	}
	_size = size;
	_arr = new int[_size];
}

גישה

בשלב הבא, נרצה לאפשר גישה למידע - הכנסה והוצאה. ההוצאה היא פשוטה מאוד, ומתבצעת באמצעות גישה ישירה למערך (ללא שום בדיקה):

/**
 * Returns element at the given location
 * @param loc Location of element to retrieve
 * @return Element at the given location
 */
public int get(int loc) {
	return _arr[loc];
}

כשמגיעים להכנסת איברים, לעומת זאת, הדברים מסתבכים. כפי שהגדרנו, המחלקה שלנו חייבת לתמוך גם בהכנסת איברים למקומות שהאינדקס שלהם עובר את הגודל הנוכחי של המערך הפנימי שלנו. במקרה זה, נזדקק בשלב הראשון לשיטה שתדע לשנות את גודלו של המערך הפנימי.

// Resize the vector array
private void resizeArray(int newSize) {
	int tempArr[] = new int[newSize];
	for(int i=0; i<_size; i++) {
		tempArr[i] = _arr[i];
	}
	_arr = tempArr;
	_size = newSize;
}

השיטה הזו, שאינה גלויה למשתמש מחוץ למחלקה, מבצעת את הגדלת המערך בצורה הבאה: יוצרת מערך חדש בגודל הרצוי, מעתיקה את תוכן המערך הישן למערך החדש, ואז הופכת את המערך החדש, הגדול יותר, להיות המערך בו משתמשת המחלקה. נקודה אחרת נוגעת לבחירה שעשינו בקשר להגדלת המערך: בכל פעם שאנו מגדילים את המערך, אנו מגדילים אותו הרבה יותר מהדרוש - למעשה, מכפילים את הגודל שהיינו צריכים. בפשטות, הסיבה היא שאנו רוצים לאזן בין הצורך להגדיל את המערך כמה שפחות פעמים (כי בכל פעם צריך להעתיק את כולו), לבין הצורך למנוע בזבוז של זיכרון. כעת, בעזרת שיטה זו, נממש את ההכנסה:

/**
 * Put data element at the given location
 * @param loc Location of element to put
 * @param data Data to put in that location
 */
public void put(int loc, int data) {
	if(loc < _size) {
		_arr[loc] = data;
	}
	else {
		int newSize = loc * 2;
		resizeArray(newSize);
		_arr[loc] = data;
	}

}

הקוד המלא של התוכנית

/**
 * Implements a simple vector
 * 
 * @author Johnny Zoo
 */
public class MyVector {
	// Array holding all data elements
	private int _arr[];
	// Current size of vector
	private int _size;

	/**
	 * Constructor
	 * @param size Initial size of vector
	 */
	public MyVector(int size) {
		if(size < 0) {
			reportError("Illegal size");
		}
		_size = size;
		_arr = new int[_size];
	}
	
	/**
	 * Returns element at the given location
	 * @param loc Location of element to retrieve
	 * @return Element at the given location
	 */
	public int get(int loc) {
		return _arr[loc];
	}
	
	/**
	 * Put data element at the given location
	 * @param loc Location of element to put
	 * @param data Data to put in that location
	 */
	public void put(int loc, int data) {
		if(loc < _size) {
			_arr[loc] = data;
		}
		else {
			int newSize = loc * 2;
			resizeArray(newSize);
			_arr[loc] = data;
		}
		
	}
	
	/**
	 * @return Vector current size
	 */
	public int getSize() {
		return _size;
	}
	
	// Resize the vector array
	private void resizeArray(int newSize) {
		int tempArr[] = new int[newSize];
		for(int i=0; i<_size; i++) {
			tempArr[i] = _arr[i];
		}
		_arr = tempArr;
		_size = newSize;
	}
	
	// Print error message and quit
	private void reportError(String err) {
		System.err.println(err);
		System.exit(1);
	}
}

מחיר

כמו לכל דבר, גם ליתרונות שנותן לנו מערך שגדל מעצמו יש מחיר מסויים: כל הגדלה של המערך גוררת איתה העתקה של כל איברי המערך, פעולה שבטווח הארוך עשויה לגזול משאבים רבים. למזלנו, פעולות כאלה מתבצעות מעט יחסית. בנוסף, אנו מסוגלים לגשת לאיברי הוקטור בצורה נוחה ומהירה, בדיוק כמו שעשינו עם איברי המערך. כעת זה נראה מובן מאליו, אך כשנלמד על מבני נתונים נוספים, נראה שלא תמיד כך הדבר.

רשימה מקושרת

רשימה מקושרת פשוטה. התאים מכילים את המידע 12, 99, ו-37. החוליה "12" היא החוליה הראשונה - ראש הרשימה.

רשימה מקושרת מבוססת על גישה שונה. חשבו על שרשרת של חוליות שאנו יכולים להרכיב ולפרק כרצוננו, כאשר החוליות מכילות את המידע שאנו רוצים להחזיק. אין כאן בעייה של מקום (כל עוד נותר למחשב זיכרון פנוי) - אם נרצה להוסיף מידע חדש, כל מה שצריך לעשות זה ליצור חוליה חדשה ולהוסיף אותה לשרשרת החוליות שלנו.

הסבר

רשימה מקושרת (מהסוג הפשוט ביותר) בנויה מאוסף של חוליות, כאשר כל חוליה מחזיקה שני פריטים: הפריט הראשון הוא המידע שהרשימה שומרת. הפריט השני הוא הפניה לאיבר הבא בשרשרת - החוליה הבאה. התוכנית צריכה לזכור רק איבר אחד: האיבר הראשון ברשימה. ברגע שאנו יודעים מה האיבר הראשון ברשימה ניתן לדלג חוליה אחרי חוליה לכל מקום ברשימה. החוליה האחרונה מצביעה על מקום ריק, וכך ניתן לדעת מתי הגענו לסוף הרשימה. נעיר כי ברשימה מהסוג הזה הדילוגים מתבצעים רק בכיוון אחד: כל חוליה של הרשימה יודעת מהי החוליה שאחריה, אך לא מה החוליה שלפניה. קיימים גם סוגים אחרים של רשימות, אולם לעת עתה נתמקד בסוג הפשוט ביותר.

הוספה של איבר לרשימה מקושרת. במקרה זה נוסף האיבר למקום שאינו ראש הרשימה.

כדי להוסיף איבר, ניצור חוליה חדשה, ונכניס אותה למקום הרצוי ברשימה, כאשר החלק החשוב הוא עדכון של החוליה שלפניה כך שתצביע עליה, וקביעה של המצביע של החוליה החדשה כך שיצביע על החוליה הבאה בתור. בתוכנית שלנו, בה נבחר להוסיף תמיד איברים רק לראש הרשימה, נקבע שהחוליה הבאה אחרי החוליה שיצרנו היא זו שהייתה ראש הרשימה, ונשנה את ראש הרשימה להיות החוליה החדשה.

מחיקה של איבר מרשימה מקושרת.

כדי להוציא איבר, אין צורך למחוק אותו בפועל: כל מה שצריך לעשות זה לשנות את החוליה שמצביעה על האיבר אותו אנחנו רוצים למחוק, כך שתצביע על האיבר שאחריו. כאשר אין אף איבר שמצביע על חוליה כלשהי - היא נמחקת (אספן הזבל של ג'אווה דואג בשלב מסויים לפינוייה מהזיכרון).

הפעולה האחרונה היא חיפוש של איבר. במקרה זה, אין ברירה: יש להתחיל מראש הרשימה ולחפש חוליה אחר חוליה אחרי האיבר הרצוי. פעולה נוספת שנהוג לספק היא בדיקה האם הרשימה ריקה, וגם אותה נממש.

מימוש

1.חוליות

בשלב הראשון, נזדקק לדרך לממש את החוליות של הרשימה. לשם כך, נשתמש בכלי חדש - מחלקה פנימית. מחלקות פנימיות הן מחלקות שנכתבות בשלמותן בתוך מחלקה קיימת. לא נעמיק כאן בנושא ובתכונות המחלקות הפנימיות בג'אווה, אלא נסתפק בשימוש שנראה כאן. את המחלקה הפנימית שלנו נסמן כ-private, ולכן הגישה אליה תהייה אפשרית אך ורק מתוך המחלקה החיצונית שבתוכה היא כתובה. המחלקה שלנו, שתיקרא "Node" (שם מקובל לחוליות של רשימות מקושרות), תכיל שני שדות בלבד - נתונים (מסוג int) וקישור לחוליית ההמשך (מסוג Node). צורת העבודה איתה דומה לצורת העבודה עם כל מחלקה אחרת (בהבדלים שונים, בהם לא ניגע כאן), אך השימוש דווקא במחלקה פנימית עדיף, כיוון שהוא שומר על כימוס - מניעה של גישה למחלקה Node ממחלקות אחרות.

/**
 * Implements a node in the list
 */
private class Node {
	
	public Node(int data) {
		_data = data;
		_next = null;
	}
	
	int _data;
	Node _next;
}

הרשימה והבנאי

התוכנית מכילה רק שדה אחד עבור הרשימה: השדה _head, שמכיל את ראש הרשימה (וכך, למעשה, נותן לנו גישה לכל הרשימה):

// Head of the list
private Node _head;

נכתוב גם בנאי לרשימה (שייצור רשימה ריקה):

/**
 * Simple constructor
 */
public MyLinkedList() {
	_head = null;
}

בנוסף, ניתן למשתמש כלי לבדוק האם רשימה היא ריקה או לא. זוהי בדיקה פשוטה מאוד עבורנו - אם ראש הרשימה הוא ריק (כלומר, null) - הרשימה ריקה. אם לא - הרשימה אינה ריקה.

/**
 * @return True if the list is empty, else if not
 */
public boolean isEmpty() {
	return (_head == null);
}

הוספת איבר

כפי שתיארנו קודם, הוספת איבר תיעשה על ידי יצירת חוליה חדשה אותה נשים במקום ראש הרשימה. אם הרשימה ריקה (כלומר, ראש הרשימה הוא null) - ניצור את החוליה ונבחר אותה להיות ראש הרשימה. נעיר כאן כי במקרים רבים, הוספת איבר מתבצעת בצורה אחרת - איברים חדשים נוספים לפי סדר, לסוף הרשימה, או לכל מקום אחר בו יבחרו המתכנתים. במקרה זה, לשם הפשטות, ומאחר שאין לנו צורך שהרשימה תהייה מסודרת, נוסיף את האיבר לתחילת הרשימה.

/**
 * Add new element to the list
 * @param data Data to add
 */
public void addElement(int data) {
	if(isEmpty()) {
		_head = new Node(data);
	}
	else {
		Node newNode = new Node(data);
		newNode._next = _head;
		_head = newNode;
	}
}

הסרת איבר

גם הסרת איבר מהרשימה תתבצע כפי שתיארנו: נחפש את האיבר ברשימה, ונסיר אותו באמצעות העברת המצביע לאיבר אותו אנחנו רוצים למחוק כך שיצביע על האיבר שאחריו (או, במקרה וזהו האיבר האחרון ברשימה - יצביע על null). מקרה יוצא דופן הוא זה בו צריך להסיר את ראש הרשימה. במקרה זה המצביע לאיבר הוא המשתנה _head, ואז כל שצריך לעשות הוא לקבוע את _head להיות האיבר השני ברשימה (וכך להיפטר מהאיבר הראשון, אותו רצינו למחוק).

/**
 * Removes a given element from the list
 * @param data Data to remove
 * @return True if this data removed, false if not
 */
public boolean removeElement(int data) {
	if(isEmpty()) return false;
	Node runner = _head;
	// If the data is in the head - we can just remove the head
	if(runner._data == data) {
		_head = _head._next;
		return true;
	}
	// The data is not in the first node
	else {
		Node prev = _head;
		runner = _head._next;
		while(runner != null) {
			if(runner._data == data) {
				// Now the previous node points on the one after
				// the one we removed
				prev._next = runner._next;
				return true;
			}
			runner = runner._next;
			prev = prev._next;
		}
	}
	// The element we wanted to remove is not in list
	return false;
}

חיפוש

חיפוש מתבצע על ידי מעבר סדרתי על איברי הרשימה.

/**
 * Search the list for a given element
 * @param data Data to find
 * @return True if this element is in list, false if not
 */
public boolean contains(int data) {
	Node runner = _head;
	while(runner != null) {
		if(runner._data == data) {
			return true;
		}
		runner = runner._next;
	}
	return false;
}

ייתכן ושמתם לב לשכפול מיותר של קוד - ניתן היה לכתוב שיטה פרטית לחיפוש איברים, וכך למנוע את שכפולן של השורות הזהות מפונקציית המחיקה ופונקציית החיפוש. כאן, למטרות לימוד, נכתב הקוד כפי שנכתב.

גישה

נרצה גם דרך לגשת לאיברי הרשימה השונים.

/**
 * Returns the element at the given index
 * 
 * @param loc
 *            Index of data to retrieve
 * @return The data that the element at the given index holds
 */
public int elementAt(int loc) {
	Node runner = _head;
	if (loc < 0)
		throw new IndexOutOfBoundsException();
	for (int i = 0; i > loc; i++) {
		runner = runner._next;
		if (runner == null)
			throw new IndexOutOfBoundsException();
	}
	return runner._data;
}

נשים לב שבמקרה בו ניסינו לגשת לאיבר שמספרו לא חוקי, נזרקה חריגה. בהמשך תוכלו ללמוד יותר על נושא החריגות.

הקוד המלא של התוכנית

/**
 * Implements a simple singly-linked list
 * @author Johnny Zoo
 */
public class MyLinkedList {

	/**
	 * Implements a node in the list
	 */
	private class Node {

		public Node(int data) {
			_data = data;
			_next = null;
		}

		int _data;
		Node _next;
	}

//	Head of the list
	private Node _head;

	/**
	 * Simple constructor
	 */
	public MyLinkedList() {
		_head = null;
	}

	/**
	 * @return True if the list is empty, else if not
	 */
	public boolean isEmpty() {
		return (_head == null);
	}

	/**
	 * Add new element to the list
	 * @param data Data to add
	 */
	public void addElement(int data) {
		if(isEmpty()) {
			_head = new Node(data);
		}
		else {
			Node newNode = new Node(data);
			newNode._next = _head;
			_head = newNode;
		}
	}

	/**
	 * Removes a given element from the list
	 * @param data Data to remove
	 * @return True if this data removed, false if not
	 */
	public boolean removeElement(int data) {
		if(isEmpty()) return false;
		Node runner = _head;
		// If the data is in the head - we can just remove the head
		if(runner._data == data) {
			_head = _head._next;
			return true;
		}
		// The data is not in the first node
		else {
			Node prev = _head;
			runner = _head._next;
			while(runner != null) {
				if(runner._data == data) {
					// Now the previous node points on the one after
					// the one we removed
					prev._next = runner._next;
					return true;
				}
				runner = runner._next;
				prev = prev._next;
			}
		}
		// The element we wanted to remove is not in list
		return false;
	}

	/**
	 * Returns the element at the given index
	 * 
	 * @param loc
	 *            Index of data to retrieve
	 * @return The data that the element at the given index holds
	 */
	public int elementAt(int loc) {
		Node runner = _head;
		if (loc < 0)
			throw new IndexOutOfBoundsException();
		for (int i = 0; i < loc; i++) {
			runner = runner._next;
			if (runner == null)
				throw new IndexOutOfBoundsException();
		}
		return runner._data;
	}

	/**
	 * Search the list for a given element
	 * @param data Data to find
	 * @return True if this element is in list, false if not
	 */
	public boolean contains(int data) {
		Node runner = _head;
		while(runner != null) {
			if(runner._data == data) {
				return true;
			}
			runner = runner._next;
		}
		return false;
	}

	/**
	 * Prints the whole list
	 */
	public void printList() {
		Node runner = _head;
		System.out.print("[ ");
		while(runner != null) {
			System.out.print(runner._data + " => ");
			runner = runner._next;
		}
		System.out.println("]");
	}

}

מחיר

היתרון העיקרי של הרשימה המקושרת הוא המודולריות שלה: קל מאוד להוסיף ולהסיר איברים חדשים, בלי שיש צורך לדעת מראש כמה איברים יהיו, ויותר מזה - גודל הרשימה הוא בדיוק לפי גודל הקלט. עם זאת, ניתן להבחין בשני חסרונות עיקריים של הרשימה המקושרת: חסרון ראשון הוא שכל חוליה מחזיקה מידע נוסף (מצביע לחוליה הבאה), ולכן נפח הזיכרון הדרוש גדול יותר. חיסרון שני הוא הגישה הלא נוחה לאיברי הרשימה: בכל פעם שנרצה לחפש או להסיר איבר - נצטרך לעבור חוליה אחר חוליה עד שנמצא (או שנבין שהאיבר המבוקש כלל לא נמצא). ברשימות ארוכות החיפוש הזה עשוי לארוך זמן רב (באופן יחסי).

סיכום

ראינו כאן שתי צורות חדשות לאחסון של נתונים. כמו במקרים רבים, אין יתרון מובהק לאפשרות זו או אחרת. שני הפתרונות האלה קלים למימוש, וכל אחד מהם יתאים למצבים אחרים. הבחירה, כמו תמיד, צריכה להיעשות על פי הצורך הנוכחי. שימו לב שקיימות צורות רבות בהן ממומשים מבני הנתונים האלה, וכאן הוצגו רק הצורות הבסיסיות ביותר (שעבור מרבית המקרים לא יהיו שימושיות). מכיוון שהשימוש במבנים אלה נפוץ מאוד, הספרייה הסטנדרטית של ג'אווה מספקת מימוש מוכן שלהן (עם שורה ארוכה הרבה יותר של תכונות) - Vector ו-LinkedList. בהמשך הספר נראה איך להשתמש בהן (השימוש בהן דורש הבנה של נושא הגנריות, נושא שעדיין לא נלמד).

הפרק הקודם: בנאים

מבני נתונים

הפרק הבא: הורשה