Posts 학원 #31일차: 연결리스트, 스택, 큐 자료구조
Post
Cancel

학원 #31일차: 연결리스트, 스택, 큐 자료구조

Sep 2, 2020 2020-09-02T00:00:00+08:00 by hayeon_kim
19 min

v19. LinkedList 자료구조 사용하기

LinkedList 란?

연결 리스트 는

  • 노드(node) 를 이용해 데이터와 데이터를 연결하는 방식으로 데이터 목록을 관리한다.
  • 각각의 노드는 데이터와 다음 노드의 주소를 갖고 있다.
  • 배열과 달리 데이터를 추가할 때 마다 노드를 늘리는 방식이기 때문에 메모리를 효율적으로 사용한다.
  • 노드와 노드를 연결하는 방식이기 때문에 데이터의 삽입, 삭제가 빠르다.
  • 배열의 비해 데이터 조회 속도는 느리다. 배열의 경우 인덱스를 통해 바로 데이터를 찾을 수 있지만, 연결 리스트에서는 노드의 연결 고리를 따라가야 하기 때문에 조회 속도가 느리다.
  • 데이터의 삽입, 삭제가 잦고 데이터가 지속적으로 추가되는 경우 배열 방식 보다는 연결 리스트 방식이 낫다.

실습 목표

  • 연결 리스트 구현을 통해 연결 리스트 자료 구조의 구동 원리를 이해한다.
  • 배열 방식과 연결 리스트 방식의 장단점을 이해한다.
  • 또한 레퍼런스를 이용하여 객체를 다루는 것을 연습한다.
  • 중첩 클래스의 활용법을 연습한다.
  • 자바에서 제공하는 java.util.LinkedList 클래스의 이해도를 높인다.

실습 내용

  • java.util.LinkedList 를 모방하여 LinkedList 를 구현한다.
  • 기존의 XxxHandler 클래스에서 사용하는 ArrayList 를 LinkeList 로 교체한다.

MyLinkedList의 toArray(E[] arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

  @SuppressWarnings("unchecked")
  public E[] toArray(E[] arr) {
      // 사이즈가 작을 때는 새 배열을 만들어서 넣는다.
      // 따라서 파라미터와 리턴값 객체는 다르다.
    if (arr.length < this.size()) {
      // 다음과 같이 배열의 타입을 엄격히 형변환해도 된다.
      //Class<E[]> arrayClassInfo = (Class<E[]>) arr.getClass();
      //Class<E[]> arrayItemClassInfo = (Class<E[]>)arrayClassInfo.getComponentType();
      
      // 그러나 조회용으로 사용할 것이라면 굳이 리턴 값에 대해 제네릭 형변환을 엄격히 할 필요 없다.
      //Class<?> arrayClassInfo = arr.getClass();
      //Class<?> arrayItemClassInfo =arrayClassInfo.getComponentType();
      
      //arr = (E[]) Array.newInstance(arrayItemClassInfo, this.size());
      
      // => 그냥 다음과 같이 간략하게 표현하는 것이 코드를 읽기 편하다.
      arr = (E[]) Array.newInstance(arr.getClass().getComponentType());
    }
    
      // 사이즈가 작지 않을 경우 파라미터와 리턴값 객체는 같다.
    Object[] originArr = this.toArray();
    for (int i = 0; i < this.size(); i++) {
      arr[i] = (E) originArr[i];
    }
    return arr;
  }

다음은 LinkedList에 대한 테스트 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

public class MyLinkedListTest3 {
  public static void main(String[] args) {
    MyLinkedList<String> list = new MyLinkedList<>();

    list.add("aaa");
    list.add("bbb");
    list.add("ccc");
    list.add("ddd");
    //list.add(new Integer(100)); // 컴파일 오류!

    System.out.println(list.get(0));
    System.out.println(list.get(1));
    System.out.println(list.get(2));
    System.out.println(list.get(3));
    //System.out.println(list.get(-1));
    //System.out.println(list.get(4));
    System.out.println("---------------------");

    print(list); // aaa, bbb, ccc, ddd,

    System.out.println("---------------------");

    list.add(2, "eee"); // aaa, bbb, eee, ccc, ddd,
    list.add(0, "fff"); // fff, aaa, bbb, eee, ccc, ddd,
    list.add(6, "ggg"); // fff, aaa, bbb, eee, ccc, ddd, ggg
    list.add("hhh"); // fff, aaa, bbb, eee, ccc, ddd, ggg, hhh
    print(list);

    System.out.println("---------------------");

    System.out.println(list.remove(4)); // fff, aaa, bbb, eee, ddd, ggg, hhh
    print(list);

    System.out.println(list.remove(0)); // aaa, bbb, eee, ddd, ggg, hhh
    print(list);

    System.out.println(list.remove(5)); // aaa, bbb, eee, ddd, ggg
    print(list);

    System.out.println("---------------------");

    System.out.println(list.set(1, "xxx")); // aaa, xxx, eee, ddd, ggg
    print(list);

    System.out.println(list.set(0, "yyy")); // aaa, xxx, eee, ddd, ggg
    print(list);

    System.out.println(list.set(4, "zzz")); // aaa, xxx, eee, ddd, ggg
    print(list);

    System.out.println("---------------------");

    print2(list.toArray());

    System.out.println("---------------------");

    print3(list);

  }

  static void print(MyLinkedList<String> list) {
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i) + ",");
    }
    System.out.println();
  }

  static void print2(Object[] arr) {
    for (Object obj : arr) {
      System.out.print(obj + ",");
    }
    System.out.println();
  }

  static void print3(MyLinkedList<String> list) {
    // => 복사할 항목의 개수 만큼 배열을 만들어 전달하면 
    //    ArrayList는 새 배열을 만들지 않고 우리가 준 배열에 값을 담아 준다.
    //String[] arr = new String[list.size()];
    //String[] arr2 = list.toArray(arr);

    // => 복사할 항목의 개수 보다 작은 크기의 배열을 주면
    //    ArrayList는 새 배열을 만들어 값을 복사한 다음 리턴한다.
    //String[] arr = new String[2];
    //String[] arr2 = list.toArray(arr);

    // => 보통 다음 방식으로도 개발자들이 많이 사용한다.
    String[] arr2 = list.toArray(new String[] {});

    //System.out.println(arr == arr2);

    for (Object obj : arr2) {
      System.out.print(obj + ",");
    }
    System.out.println();
  }
}

제네릭의 제한

제네릭 타입을 배열을 생성하는 것은 허용되지 않는다. 이는 new 연산자 때문인데, 이 연산자는 컴파일 시점에 타입 E가 정확히 무엇인지 알아야 한다. 그런데 위에 코드에 정의된 MyLinkedList<E> 클래스를 컴파일하는 시점에는 E가 무엇이 될 지 전혀 알 수 없다. instanceof 연산자도 new 연산자와 같은 이유로 E를 피연산자로 사용할 수 없다.

그렇다면 꼭 지네릭 배열을 생성해야할 필요가 있을 때는, new 연산자 대신 ‘Reflection API’의 newInstance()와 같이 동적으로 객체를 생성하는 메서드로 배열을 생성하거나, Object배열을 생성해서 복사한 다음에 T[]로 형변환하는 방법 등을 사용한다.

v20. 스택 자료구조 구현과 활용

스택(stack)이란?

  • LIFO(Last In First Out) 방식으로 데이터를 넣고 꺼낸다.
  • 데이터를 넣는 것을 push라고 하고, 데이터를 꺼내는 것을 pop이라 한다.
  • 보통 입력한 역순으로 데이터를 꺼내야 하는 상황에서 이 자료구조를 사용한다.
  • 예)
    • JVM 스택 메모리 영역에서 메서드 호출을 관리할 때
    • 웹 브라우저에서 이전 페이지로 따라 올라 갈 때
    • 자바스크립트에서 이벤트를 처리할 때 버블링 단계를 수행(부모 엘리먼트를 따라 올라가면서 처리하는 것)

실습 목표

  • 스택(stack) 자료구조를 구현하고 구동 원리를 이해한다.
  • Object.clone() 메서드의 용도와 인스턴스를 복제하는 방법을 배운다.
  • 얕은 복제(shallow copy)와 깊은 복제(deep copy)의 차이점을 이해한다.

실습

  • java.util.Stack 을 모방하여 Stack 클래스를 구현한다.
  • 스택을 이용하여 사용자가 입력한 명령을 보관한다.
  • 사용자가 입력한 명령을 최신순으로 출력하는 history 명령을 추가한다.

history 명령 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 사용자가 입력한 명령을 보관할 commandList를 
// LinkedList 자료구조로 생성
LinkedList commandList = new LinkedList();

loop: while (true) {
	String command = Prompt.inputString("명령> ");
	// 사용자가 명령어를 입력할 때마다 commandList에 추가
    commandList.add(command);
	swtich (command) {
        //....
        // 사용자가 history를 입력할 시
        // 사용자가 입력한 명령어를 "최신순으로" 출력하는
        // printCommandHistory() 메서드 호출
      	case "history":
        	printCommandHistory(commandList);
			break;
        //...
    }

LinkedList 이용

1
2
3
4
5
6
7
8
9
10
11
12

  private static void printCommandHistory(LinkedList commandList) {
    for (int i = commandList.size() - 1, count = 1; i >= 0; i--, count++) {
      System.out.println(commandList.get(i));
      if (count % 5 == 0) {
        String response = Prompt.inputString(":");
        if (response.equalsIgnoreCase("q")) {
          break;
        }
      }
    }
    
  }

MyStack에 clone() 선언 전

1
2
3
4
5
6
7
8
9
10
11
12

  private static void printCommandHistory(Stack commandList) {
    for (int count = 1; !commandList.empty(); count++) {
      System.out.println(commandList.pop());
      if (count % 5 == 0) {
        String response = Prompt.inputString(":");
        if (response.equalsIgnoreCase("q")) {
          break;
        }
      }
    }
    
  }

Stack 자료구조를 사용할 경우, LinkedList를 사용할 때보다 저장되어 있는 객체를 최신순으로 꺼내기 간편하다. 그러나 스택은 한 번 pop()하면 데이터가 제거된다. 따라서 복제본을 만들어 사용할 필요가 있다. 따라서 아래와 같이 Stack 클래스에 clone() 메서드를 오버라이딩하였다.

MyStack의 clone() 사용: 얕은 복제(shallow copy)

1
2
3
4

  @Override
  public MyStack clone() throws CloneNotSupportedException {
	return (MyStack) super.clone();
  }

위와 같이 clone() 메서드를 오버라이딩할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  private static void printCommandHistory(Stack commandList) {
    try {
      // 스택은 한 번 pop()하면 데이터가 제거된다.
      // 따라서 복제본을 만들어 사용한다.
      // 또한 clone() 메서드는 복제 작업 중 오류가 발생하면 예외를 발생시키기 때문에
      // try... catch.. 블록으로 처리한다.
      Stack commandStack = commandList.clone();
      for (int count = 1; !commandStack.empty(); count++) {
        System.out.println(commandList.pop());
        if (count % 5 == 0 && Prompt.inputString(":").equalsIgnoreCase("q")) {
          break;
        }
      }
    } catch (Exception e) {
      System.out.println("history 명령 처리 중 오류 발생!");
    }
  }

그러나 위와 같이(얕은 복사) clone()하였을 때는 Stack이 clone()될 때 원본 데이터의 주소값들이 복사된다. 따라서 Stack의 데이터는 결국 원본 Stack과 같은 객체를 가리킨다. 따라서 pop() 메서드를 사용할 때, 원본 Stack이 가리키는 객체들까지 영향을 받게 된다. 따라서 Stack에 담겨 있는 주소값이 가리키는 객체들까지 전부 복제하는 deep copy를 해야 할 필요가 있따.

MyStack에 clone() 정의: 깊은 복제(deep copy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

  @Override
  public MyStack clone() throws CloneNotSupportedException {
    // 새 스택을 만든다.
    MyStack newStack = new MyStack();

    // 기존 스택의 값을 가져온다.
    Object[] values = this.toArray();

    // 기존 스택의 값을 새 스택에 넣는다.
    for(Object value : values) {
      newStack.push(value);
    }
    return newStack;
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  private static void printCommandHistory(Stack commandList) {
    try {
      // 스택은 한 번 pop()하면 데이터가 제거된다.
      // 따라서 복제본을 만들어 사용한다.
      // 또한 clone() 메서드는 복제 작업 중 오류가 발생하면 예외를 발생시키기 때문에
      // try... catch.. 블록으로 처리한다.
      Stack commandStack = commandList.clone();
      for (int count = 1; !commandStack.empty(); count++) {
        System.out.println(commandList.pop());
        if (count % 5 == 0 && Prompt.inputString(":").equalsIgnoreCase("q")) {
          break;
        }
      }
    } catch (Exception e) {
      System.out.println("history 명령 처리 중 오류 발생!");
    }
  }

제네릭 문법 사용

최종적으로 제네릭 문법을 사용해 완성한 Stack 자료는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

package com.eomcs.util;

public class Stack<E> extends LinkedList<E> implements Cloneable {
  public E pop() {
    if (size() == 0) {
      return null;
    }
    return remove(size() - 1);
  }

  public boolean push(E e) {
    return add(e);
  }

  public E peek() {
    return get(size() - 1);
  }

  public boolean empty() {
    return size() == 0;
  }

  @SuppressWarnings("unchecked")
  @Override
  public Stack<E> clone() throws CloneNotSupportedException {
    Stack<E> newStack = new Stack<E>();
    Object[] values = toArray();
    for (Object value : values) {
      newStack.push((E) value);
    }
    return newStack;
  }
}

다음은 Stack이 잘 작동하는 지 알아보기 위한 테스트코드이다. 값을 조회하는 용도의 메서드이기 때문에 다음과 같이 와일드카드 타입 <?>을 지정해도 무방하다. (<?>를 지정할 경우 add()메서드와 같이 컴파일 단계에서 타입 검사가 필요한 메서드는 사용할 수 없다. => 컴파일 에러가 난다!)

1
2
3
4
5
6

static void print(MyStack<?> stack) {
    for (int i = 0; i < stack.size(); i++) {
        System.out.println(stack.get(i) + ", ");
    }
    System.out.println();
}

v21. 큐 자료구조 구현과 활용

이번 훈련에서는 큐(queue) 방식으로 데이터를 저장하는 자료 구조를 만들어보자.

큐(queue) 는

  • FIFO(First In First Out) 방식으로 데이터를 넣고 꺼낸다.
  • 데이터를 넣는 것을 offer라고 하고 목록의 맨 끝에 추가한다.
  • 데이터를 꺼내는 것을 poll이라 하고 목록의 맨 앞의 값을 꺼낸다.
  • 보통 입력한 순으로 데이터를 꺼내야 하는 상황에서 이 자료구조를 사용한다.
  • 예)
    • 등록된 예약을 처리할 때
    • 네트워킹에서 연결된 순서대로 소켓을 승인하고 처리할 때

실습 목표

  • 큐(queue) 자료구조를 구현하고 구동 원리를 이해한다.
  • Object.clone() 메서드의 용도와 인스턴스를 복제하는 방법을 배운다.
  • 얕은 복제(shallow copy)와 깊은 복제(deep copy)의 차이점을 이해한다.

clone() 메서드 없이 구현

1
2
3
4
5
6
7
8

  private static void printCommandHistory2(Queue commandList2) {
    for (int count = 1; commandList2.size() > 0; count++) {
      System.out.println(commandList2.poll());
      if (count % 5 == 0 && Prompt.inputString(":").equalsIgnoreCase("q")) {
        break;
      }
    }
  }

printCommandHistory2() 메서드 안에서 poll()로 값을 출력하였을 경우, queue 자료구조에 담겨 있는 객체들이 사라진다. poll()메서드 내부적으로 remove()를 통해 값을 꺼내서 버리기 때문이다. 따라서 원본 queue 객체를 복사한 객체를 사용하여 원본 객체은 손 대지 않도록 해야 한다. Object의 clone() 메서드를 오버라이딩 해서 메서드 안에서 사용할 객체를 복제할 수 있도록 한다.

clone() 메서드 사용: shallow copy

1
2
3
4

@Override
public Queue clone() throws CloneNotSupportedException{
	return (Queue) super.clone();
}
  • MyQueue는 MyLinkedList를 상속받았고, MyLinkedList의 경우 노드와 노드 사이를 연결해야 하기 때문에 단순히 ‘shallow copy’를 수행해서는 안 된다.
  • 얕은 복사를 할 경우 값을 조회할 때 poll()를 사용하였을 경우 원본 queue 객체 또한 영향을 받게 된다.

clone() 메서드 사용: deep copy

1
2
3
4
5
6
7
8
9

@Override
public Queue clone() throws CloneNotSupportedException{
	Queue newQueue = new Queue();
	Object[] values = toArray();
	for (Object value : values) {
  		newQueue.offer(value);
	}
	return (Queue)newQueue;
}

제네릭 문법 적용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

package com.eomcs.util;

public class Queue<E> extends LinkedList<E> implements Cloneable {

  public boolean offer(E e) {
    return add(e);
  }

  public E poll() {
    if (size() == 0)
      return null;
    return remove(0);
  }

  public E peek() {
    if (size() == 0)
      return null;
    return get(0);
  }

  @SuppressWarnings("unchecked")
  @Override
  public Queue<E> clone() throws CloneNotSupportedException {
    Queue<E> newQueue = new Queue<>();
    Object[] values = toArray();
    for (Object value : values) {
      newQueue.offer((E) value);
    }
    return newQueue;
  }
}
bitcamp
bitcamp java
This post is licensed under CC BY 4.0 by the author.
Recent Update
Contents

학원 #30일차: CRUD, 제네릭문법

학원 #32일차: 일반화, 추상 클래스와 메서드, 인터페이스

Loading comments from Disqus ...