Collection

자바 컬렉션(Java Collections)은 자바에서 그룹화된 객체들의 집합을 효율적으로 관리하고 조작하기 위해 제공되는 프레임워크로 프로그래밍에서 자주 사용되는 자료구조를 미리 구현해놓았다

링크드 리스트

배열 리스트의 단점

• 필요한 배열의 크기를 미리 지정해야만 한다
• 사용되지 않는 공간은 낭비된다
• 배열을 앞이나 중간에 추가/삭제 시 배열 전체의 값이 이동해야 한다

연결 리스트

• 낭비되는 메모리 없이 필요한 만큼의 메모리 공간만 확보해서 사용
• 데이터 추가 및 삭제 시에도 효율적인 자료구조
• 노드와 노드의 연결로 리스트를 만드는 것

public class Node {
	Object item;
    Node next;
}

Node 는 내부에 저장할 데이터인 item 과
다음 노드의 참조인 next 를 가진다

1. Node 인스턴스 생성 후 item 에 'A'(값) 추가
2. 'A' 인스턴스의 next 에 새로운 Node 인스턴스 생성
3. 'A'.next.item 에 'B'(값) 추가

이와 같은 방법으로 Node 를 순차적으로 연결한다
'A' 인스턴스의 next 호출 시 'B' 를 참조할 수 있게 된다
이렇게 노드 연결의 체이닝을 통해
연결 리스트를 구현한다

public class Node {

  Object item;
  Node next;

  public Node(Object item) {
    this.item = item;
  }
}

public static void main(String[] args) {
    Node head = new Node("a");
    head.next = new Node("b");
    head.next.next = new Node("c");

    Node node = head;
    while (node != null) {
      System.out.println(node.item);
      node = node.next;
    }
  }

노드 연결상태 확인

public class Node {

  Object item;
  Node next;

  public Node(Object item) {
    this.item = item;
  }

  @Override
  public String toString() {
    return "Node{" +
        "item=" + item +
        ", next=" + next +
        '}';
  }

public static void main(String[] args) {
    Node head = new Node("a");
    head.next = new Node("b");
    head.next.next = new Node("c");

    System.out.println(head.toString());
  }

toString() 출력 결과

Node{item=a, next=Node{item=b, next=Node{item=c, next=null}}}

toSring() head 에서만 실행하지만
각 참조에서 모두 toString() 이 실행된다

자바에서 객체를 문자열로 표현하려고 할 때, 해당 객체의 toString() 메서드가 암묵적으로 호출되기 때문에 연쇄적으로 참조하고 있는 인스턴스의 모든 toString() 이 순차적으로 호출된다

StringBuilder 사용

toString 을 직접 오버라이딩해서 출력

public class Node {

  Object item;
  Node next;

  public Node(Object item) {
    this.item = item;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    Node current = this;
    sb.append("[");
    while (current != null) {
      sb.append(current.item);

      if (current.next != null) {
        sb.append("=>");
      }
      current = current.next;
    }
    sb.append("]");
    return sb.toString();
  }
}

연결 리스트의 단점

• 데이터 조회 시 하나씩 찾아야 하기 때문에 O(N)으로 비효율적
• 메모리 공간이 연속적이지 않아 관리가 비효율적, 단편화 발생 가능성
• 배열을 유지하기 위한 추가 메모리가 필요 (next 필드로 다음 노드 참조)

구현

https://github.com/lumpenop/Java-prac/

리스트 추상화

인터페이스 도입

다형성과 OCP 원칙을 활용해볼 수 있는 좋은 예제가 자료구조에 있다
자료구조에서 다형성과 OCP 원칙의 적용을 살펴본다

List 자료구조

순서가 있고, 중복을 허용하는 자료구조
ArrayList 와 LinkedList 는 내부 구현은 다르지만
사용자 입장에서 보면 같은 기능을 제공하는 리스트다
이 둘을 인터페이스로 추상화하면 다형성을 활용해 다양한 이득을 얻을 수 있다

인터페이스로 클래스 구현 시
구현하는 메서드는 @Override 어노테이션을 달아줘야 한다

• 인터페이스를 제대로 구현하였는지 타입 검사
• 구현된 메서드임을 명시적으로 알림
  두 가지 기능을 한다