Algorithm Study - Bag

Doyoon Kim·2021년 5월 30일
Javaalgorithmbagdata structure

Algorithms

목록 보기
2/2
post-thumbnail

Intro

Data and the way of handling those data are core part of programming. Sometimes, those two factors above determines program's entire efficiency- program can be inefficient when data is improperly handleded, even though the algorithm itself is extremely powerful and efficient.

In this respect, it is necessary for programmers to pay attention to Data Structure, such as Collection. Several fundamental data types involve Collections of Object. Collections of Object consist set of value, and corresponding operations - adding, removing or examining - involve handling values in collections. There are countless types of collections are existed, however, Bag, one type of collections, will be highlighted in this post.

Bag

Bag is a collection where removing items is not supported - its purpose is to provide clients with the ability to collect items and then to iterate through the collected items. Bag collects items and "periodically" process all items collected. This characterstic elevates the neccessity of implementing Linked Data Structure.

Linked Data Structure is closely related to Chain of Node. Each node contains value and pointer to the next node so that entire chain creates periodical sequence. A figure below shows simple diagram of Singly Linked Nodes.

Specifically, Linked List makes efficient implementation of Bag, Stack and Queue possible. By definition, Linked List is a recursive data structure that is either empty (null) or a node having a generic item and a reference to a linked list.

In general, proper Bag implementation need to satisfy theses requisites below.

  1. Client can add new item to the Bag.
  2. Client can test states of the Bag (ex. whether Bag is empty or not.)
  3. Client can access to all items periodically using iteration.

A simple implementation of Bag data structure below illustrates those requisites.

Simple Implementation - Bag.java

A class called Bag with generic mechanism is created for this implementation. 

public class Bag<Item> implements Iterable<Item>

One noticable thing in the code above is that Bag class implements Iterable. This brings us new question: What is the difference between Iterable and Iterator. Iterable is a simple representation of a series of data, which can be iterated over, but doesn't have a iteration state. Iterator is an object with iteration state. If Bag class implements Iteration<Item>, the object Bag will have iteration state, which leads unexpected loss of data set right after clients try to access data by using such as for-each, while, etc.,. To prevent this, Bag should not have iteration state; Bag should have potential to create itertator when it is needed.

Bag class now need few classes that enables implementation of Linked Data Structure and Linked List.

// 1. Private class for Nodes - Linked Data Structure
private class Node<Item> {
  	priavte Item data;	// data
	private Node<Item> linkNode;	//Pointer
}

// 2. Class for Linked List (In this case, Linked Iterator)
public class BagIterator<Item> implements Iterator<Item> {
	private Node<Item> current;
	
	public BagIterator(Node<Item> current) {
		this.current = current;
	}
 	
	@Override - hasNext(), next()
}

At last, in order to satisfy rest of requisties, Bag class need to implement these methods(operations).

//1. Add method that adds item to Bag.
public void add(Item data) {
	// Node is created, and linking between previous node and newly added node 
  	// is established.
}

//2. Method that examines Bag's property (This case, whether Bag is empty or not.)
public boolean isEmpty() {
	// Return True, if size() returns positive, non-zero value.
	// Return False, if size() returns zero value.
}

public int size() {
	// Return size of bag.
}

Completed implementation of Bag class and its example client code can be found at link below.

References

profile
Doyoon Kim
Student Developer
이전 포스트

Algorithm Study - Binary Search

0개의 댓글