JavaをJava 17(Collection Framework(2)、LinkedList、Stack、Queue)に変換
Collection Framework(2)
3. LinkedList
ArrayListとLinkedListはいずれもListというインタフェースから継承されて実現される.しかし,両リストの実装方式が異なり,性能も異なる.
ArrayListを振り返ると、ArrayListは本当に配列そのものによって連続した空間を配置している.
逆に、LinkedListのデータは、互いに接続された以下のオブジェクトのアドレスを有する.
class Node {
Node next; // a link to the next element
Object obj; // data
}
したがってLinkedListと呼ばれる理由はインスタンス間の接続である.
Addition and deletion with linked lists
ではなぜLinkedListを使うのでしょうか.挿入削除が有効なため
ArrayListとLinkedListはいずれもListというインタフェースから継承されて実現される.しかし,両リストの実装方式が異なり,性能も異なる.
ArrayListを振り返ると、ArrayListは本当に配列そのものによって連続した空間を配置している.
逆に、LinkedListのデータは、互いに接続された以下のオブジェクトのアドレスを有する.
class Node {
Node next; // a link to the next element
Object obj; // data
}Addition and deletion with linked lists
ではなぜLinkedListを使うのでしょうか.挿入削除が有効なため
削除するときは住所を変えるだけでいいです.
データを挿入しても、データのアドレスを接続すれば、挿入は完了します.
Types of linked lists
(Basic) linked lists
Doubly linked list: better accessibility
前後データ参照が容易です.
Doubly circular linked list
一番前と後ろを指さす方法もある.
Example 1: ArrayList vs. LinkedList
public class Lecture {
// Sequential Add
public static long add1(List<String> list) {
// 현재 시간은 Milisecond 단위로 저장한다.
long start = System.currentTimeMillis();
for(int i=0; i<1000000; i++) list.add(i+"");
long end = System.currentTimeMillis();
// 작업 시간이 반환
return end - start;
}
// Non-Sequential Add
// 500 번째부터 x를 삽입하라
public static long add2(List<String> list) {
long start = System.currentTimeMillis();
for(int i=0; i<10000; i++) list.add(500, "X");
long end = System.currentTimeMillis();
return end - start;
}
// 맨 마지막에서 부터 remove 실행
public static long remove1(List<String> list) {
long start = System.currentTimeMillis();
for(int i=list.size()-1; i>=0; i--) list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
// 앞에서부터 remove 실행
public static long remove2(List<String> list) {
long start = System.currentTimeMillis();
for(int i=0; i<10000; i++) list.remove(i);
long end = System.currentTimeMillis();
return end - start;
}
public static void main(String args[]) {
ArrayList<String> al = new ArrayList<>(2000000);
LinkedList<String> ll = new LinkedList<>();
System.out.println("=== sequential add ===");
System.out.println("ArraList : " + add1(al));
System.out.println("LinkedList: " + add1(ll));
System.out.println();
System.out.println("=== non-sequential add ===");
System.out.println("ArraList : " + add2(al));
System.out.println("LinkedList: " + add2(ll));
System.out.println();
System.out.println("=== non-sequential delete ===");
System.out.println("ArraList : " + remove2(al));
System.out.println("LinkedList: " + remove2(ll));
System.out.println();
System.out.println("=== sequential delete ===");
System.out.println("ArraList : " + remove1(al));
System.out.println("LinkedList: " + remove1(ll));
}
}
Example 2: ArrayList vs. LinkedList
public class Lecture {
public static void main(String args[]) {
//ArrayList는 따로 공간 할당
ArrayList<String> al = new ArrayList<>(1000000);
LinkedList<String> ll = new LinkedList<>();
add(al);
add(ll);
//Access Time 측정
System.out.println("=== access time ===");
System.out.println("ArrayList : " + access(al));
System.out.println("LinkedList: " + access(ll));
}
//List 객체는 superclass이기에 AL, LL 모두 삽입가능
public static void add(List<String> list) {
for(int i=0; i<100000; i++) list.add(i+"");
}
//list의 i번째 값을 가져오는 기능만 존재
public static long access(List<String> list) {
long start = System.currentTimeMillis();
for(int i=0; i<10000; i++) list.get(i);
long end = System.currentTimeMillis();
return end - start;
}
}
では、どのデータアクセス速度が速いのでしょうか.中間位置のデータが見つかった場合、ArrayListは、データが連続的に存在するため、その位置の位置を算出することができる.(エンティティ検索アルゴリズムが存在します.)
逆に、LinkedListは、データにアクセスするためにアドレスに沿って移動し続ける必要があります.
結論からもArrayListリファレンスの方が有利であることが分かる.
4. Stack and Queue
Stack:LIST IN FRIST OUTのデータ構造
どこでもデータを入力したり削除したりできるのではなく、先に入れたデータが最も遅く現れるデータ構造です.
class Stack<E>Queue:First in First outのデータ構造
先に置かれたデータは、最初に出てくる方式の資料構造です.
interface Queue<E>Methods
Example: Stack vs. Queue
public class Lecture {
public static void main(String[] args) {
// Stack은 class라서 바로 사용
Stack<String> st = new Stack<String>();
// Queue는 interface이기에 LinkedList 를 사용
Queue<String> q = new LinkedList<String>();
// 스택에 데이터 삽입
st.push("0");
st.push("1");
st.push("2");
// 큐에 데이터 삽입
q.offer("0");
q.offer("1");
q.offer("2");
System.out.println("=== Stack ===");
while(!st.empty()) System.out.println(st.pop());
System.out.println("=== Queue ===");
while(!q.isEmpty()) System.out.println(q.poll());
}
}
Example: Implementing Stack
Stackの関数は次のとおりです.
import java.util.*;
public class MyStack<E> extends Vector<E> {
// push는 데이터를 삽입하는 것이다.
public E push(E item) {
addElement(item); // defined in class Vector
return item;
}
// pop은 가장 늦게 들어온 데이터를 빼내는 것이다.
public E pop() {
E e = peek();
removeElementAt(size() - 1);
return e;
}
// empty는 stack이 비어 있는지 확인하는 것이다.
public boolean empty() {
return size() == 0;
}
// peek는 가장 마지막 성분을 반환해 주는 것이다.
public E peek() {
int len = size();
if( len == 0 ) throw new EmptyStackException();
return elementAt(len - 1);
}
// 객체가 stack안에 있는지 확인하는 것이다.
public int search(Object o) {
int i = lastIndexOf(o);
if(i >= 0) { return size() - i; }
return -1;
}
}Example: Using Stack
今度はStackを持って何ができるか見てみましょう.
public class Lecture {
public static Stack<String> back = new Stack<>();
public static Stack<String> forward = new Stack<>();
public static void main(String[] args) {
goURL("1. Google");
goURL("2. Facebook");
goURL("3. Naver");
goURL("4. Daum");
printStatus();
goBack();
System.out.println("=== After pushing 'back' ===");
printStatus();
goBack();
System.out.println("=== After pushing 'back' ===");
printStatus();
goForward();
System.out.println("=== After pushing 'forward' ===");
printStatus();
goURL("www.ABC.co.kr");
System.out.println("=== After moving to a new URL ===");
printStatus();
}
// printStatue는 back과 forward state의 성분을 보는 것이다. 그리고 current page를 보는 것이다.
public static void printStatus() {
System.out.println("back:"+back);
System.out.println("forward:"+forward);
System.out.println("current page is " + back.peek() + ".");
System.out.println();
}
// back에 모든 url을 넣고 forward는 비워준다.
public static void goURL(String url) {
back.push(url);
if(!forward.empty()) forward.clear();
}
// forward에서 데이터를 빼내고 push에 데이터를 넣는다.
public static void goForward() {
if(!forward.empty()) back.push(forward.pop());
}
// back에서 데이터를 빼내고 push에 데이터를 넣는다.
public static void goBack() {
if(!back.empty()) forward.push(back.pop());
}
}
Example: Using Queue
public class Lecture {
// Queue의 선언
static Queue<String> q = new LinkedList<String>();
static final int MAX_SIZE = 5;
public static void main(String[] args) {
System.out.println("input 'help' to display help message.");
while(true) {
System.out.print(">>");
try {
//사용자에게 입력을 받음
Scanner s = new Scanner(System.in);
// 사용자에게 받은 입력 마지막에 있는 스페이스바를 없애줌
String input = s.nextLine().trim();
// 사용자 입력이 없다면 재 실행
if("".equals(input)) continue;
// q를 입력시 시스템 종료
if(input.equalsIgnoreCase("q")) {
System.exit(0);
// help 입력시 내용을 출력
} else if(input.equalsIgnoreCase("help")) {
System.out.println(" help – displays help message.");
System.out.println(" q or Q – exit the program.");
System.out.println(" history – shows recent commands.");
}
// history 입력시 그동알 쳤던 입력들을 출력
else if(input.equalsIgnoreCase("history")) {
int i=0;
save(input);
LinkedList<String> tmp = (LinkedList<String>)q;
ListIterator<String> it = tmp.listIterator();
while(it.hasNext()) System.out.println(++i+"."+it.next());
} else {
save(input);
System.out.println(input);
}
} catch(Exception e) { System.out.println("input error."); }
}
}
// 입력값들을 저장
public static void save(String input) {
if(!"".equals(input)) q.offer(input);
if(q.size() > MAX_SIZE) q.remove();
}
} 
スキャナーを閉じないとエラーになるので注意してください.だから私たちが使わない間にScannerを閉じましょう
Priority Queue
要素が削除されると、データは優先順位で削除されます.
この構造をheapと呼ぶ.そして、この時点で、何を優先するかの基準を入れるべきです.
public class Lecture {
public static void main(String[] args) {
Queue<Integer> pq = new PriorityQueue<Integer>();
pq.offer(3);
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(4);
System.out.println(pq);
Integer i = null;
while((i = pq.poll()) != null) System.out.println(i);
}
}Reference
この問題について(JavaをJava 17(Collection Framework(2)、LinkedList、Stack、Queue)に変換), 我々は、より多くの情報をここで見つけました https://velog.io/@tonyhan18/기초-인공지능-17-9n1juha4テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol