Chapter 11. Collection Framework - 2 (컬랙션 프레임웍의 구현체의 대하여 - List)

Collection 프레임웍의 구현체

List, Set, Map 인터페이스의 구현체들을 말한다. 

 

List 인터페이스의 구현체

• ArrayList
  내부적으로 각 요소(데이터)를 Object배열(Array) 넣어서 데이터들을 연달아 (일반적인 list의 개념) 관리하는 데이터 구조.
  
  - 특징
  1. Object 배열을 사용하므로 데이터가 순차적으로 저장된다. ( 0 ~ 배열길이까지)
  2. 배열의 형태이므로 중간 위치에 데이터를 삽입하거나 삭제 할 경우 해당 인덱스 이후 데이터들을 한칸씩 미루거나, 한칸씩 당겨와야 한다. (배열의 단점)
  3. 순차적인 데이터 접근에 속도가 빠르다.
  4. 처음 ArrayList 객체 생성시 저장공간의 크기를 적절하게 설정해 주어야 한다 (데이터 삽입시 Object 배열의 크기를 초과할 경우 더 큰 크기의 새로운 배열을 생성하고 기존 데이터를 새 배열에 모두 복사 한 뒤에 삽입 인덱스가 중간일 경우 또 모든 데이터를 한칸씩 미루고 해당 인덱스에 데이터를 넣어야 하는, 이런 비효율적인 일련의 과정이 필요하다)
  
  
• LinkedList
  내부적으로 Node라는 형태의 데이터구조를 가지고 데이터를 관리하는 구현체로써
  각 Node는 기본적으로 본인 자체의 실제 데이터와 다른 데이터를 가진 Node의 주소값을 가지고 있다. (Linked List의 종류에 따라 주소값을 여러개가 될 수도 있다)
  
  - 특징
  1. 내부적으로 데이터를 노드로써 관리하므로 데이터의 중간 삽입과 삭제가 용이하다. (삽입할 위치의 이전 노드의 다음 주소값을 삽입하려는 노드의 주소값으로 치환하여 주고 삽입하는 노드는 삽입할 위치 노드의 주소값을 가리키면 된다)
  2. 중간 데이터를 처리 하기 위해선 첫 노드부터 진입하여 순차적으로 해당 노드를 찾아야 하는 단점이 있다 (배열처럼 인덱스가 존재하지 않으므로)
  
  + LinkedList는 추가적으로 발전된 Double Linked List와 Double Circular Linked List가 존재한다.

 

- ArrayList의 대한 정리 -

 

ArrayList의 메서드

주요한 메서드들은 검색만 하여도 쉽게 알 수 있으므로, 메서드가 잘 정리 되있는 블로그를 참조하여 대체하고 특별하거나 모르고 지나칠 수 있는 메서드만 추려내겠다.

 

• 주요 메서드 참조 블로그
  https://da2uns2.tistory.com/entry/Java-ArrayList-%EC%82%AC%EC%9A%A9%EB%B2%95%EA%B3%BC-%EC%A3%BC%EC%9A%94-%EB%A9%94%EC%86%8C%EB%93%9C

[Java] ArrayList 사용법과 주요 메소드

• 기타 메서드
  : ArrayList (Collection c) - 같은 Collection 인터페이스를 상속한 
  : ensureCapacity (int minCapacity) - ArrayList의 내부에 존재하는 Object 배열의 크기를 보장해준다
  
  
•  관련 코드

package ch11.practice.subPractice;

import java.util.*;

class ArrayListPractice {

    public static void main(String[] args) {
        ArrayListPractice arrayListPractice = new ArrayListPractice();
        arrayListPractice.method();
    }
    
    public void method() {
        Set set = new HashSet();

        set.add(3);
        set.add(10);
        set.add(18);
        set.add(22);
        set.add(22);
        set.add(22);

        Iterator hashSetIterator = set.iterator();

        System.out.println();
        System.out.println("==== HashSet의 요소 출력 ====");

        while (hashSetIterator.hasNext()) {
            System.out.println(hashSetIterator.next());
        }

        System.out.println("==== HashSet의 요소 출력 ====");
        System.out.println();

        System.out.println("==== ArrayList의 요소 출력 ====");

        ArrayList arrayList = new ArrayList(set);
      
        Iterator arrayListIterator = arrayList.iterator();

        while (arrayListIterator.hasNext()) {
            System.out.println(arrayListIterator.next());
        }

        System.out.println("==== ArrayList의 요소 출력 ====");

        arrayList.ensureCapacity(10); // size가 아니다. 직접적인 배열의 최소 크기를 설정한다
    }
}

 

• 결과 화면
  
  

우선 코드상에서 HashSet에 3, 10, 18, 22, 22, 22 를 순차적으로 add해 주었다. 하지만 Set의 특성상 중복이 허용 되지 않고 순서가 보장되지 않기에 18, 3, 22, 10 으로 데이터가 삽입 되었고, 그 HashSet의 참조변수인 set을 ArrayList 생성자에 넣어서 ArrayList화 시켜 주었다.

참고로 ensureCapacity는 size의 크기가 아니다. 실제 배열의 크기 (Capacity를 설정해주는것이다)

size => ArrayList 내부적으로 가지고 있는 Object배열의 현재 위치 인덱스

capacity => ArrayList 내부적으로 가지고 있는 Object배열의 실제 크기

Vector 객체를 사용하게 되면 size와 capacity 개념이 확실히 이해될것이다..

 

(Vector의 멤버 메소드에는 setSize(int size) 라는 메소드가 존재한다. 해당 메서드의 매개변수로 현재 내부 배열안에 존재하는 데이터 갯수를 무시하고 더 크게 잡으면 Iterator로 Vector 객체의 요소를 출력할시에 아무런 값이 대입되지 않은 배열의 요소도 null로써 출력한다.)

 

capacity가 size를 포함하는 개념이다

capacity > size

- LinkedList의 대한 정리 -

LinkedList

배열 형태 (배열을 내부적으로 사용하는 컬랙션 포함) 를 가지는 데이터 구조의 단점을 보완하기 위하여 만들어진 데이터 구조로써, 각 데이터가 Node 타입의 형식을 가진다.

각 노드들은 실제 데이터를 가진 변수와, 다음 노드의 주소값을 가진 변수를 가지고있다.

아래의 그림과 같은 구조이다.

 

LinkedList의 메서드

주요한 메서드들은 검색만 하여도 쉽게 알 수 있으므로, 메서드가 잘 정리 되있는 블로그를 참조하여 대체하고 특별하거나 모르고 지나칠 수 있는 메서드만 추려내겠다.

: boolean add (Object o) - 매개변수로 보내지는 요소를 LinkedList의 마지막에 추가한다

: Object get (int index) - 매개변수 값의 인덱스에 존재하는 요소를 반환.

: boolean addAll (Collection c) - 매개변수 컬렉션에 포함된 모든 요소를 해당 함수를 호출하는 LinkedList의 끝에 추가한다
: int indexOf (Object o) - 매개변수로 보내지는 요소가 몇번째에 위치하는지 인덱스를 반환

 

- Queue 인터페이스를 LinkedList로 구현하기 위해 추가적으로 생겨난 메서드 

: Object element() - LinkendList의 첫번째 요소 반환

: Object peek () - LinkendList의 첫번째 요소 반환

: boolean offer (Object o) - 매개변수 객체를 리스트의 끝에 추가

: Object poll () - LinkendList의 첫번째 요소 반환 (LinkedList)에서는 제거 된다.

: Object remove() - LinkendList의 첫번째 요소 제거

- Deque 인터페이스를 LinkedList로 구현하기 위해 추가적으로 생겨난 메서드 (설명은 직관적으로 알 수 있고 위와 겹치는 부분이 많기 때문에 생략한다)
: Object getFirst()

: Object pop () 

: boolean push (Object o) 

 

위에 회색 배경의 메서드들은 Queue, Deque 인터페이스를 LinkeList 구현체로 구현하기 위하여 추가적으로 생겨난 메서드들이다. 그러므로, List 인터페이스로써 Linked List를 사용하고 싶다면 참조변수 타입을 List로 설정하여 사용하면 될것이다.

 

 

Double LinkedList

Linked List를 보완하기 위하여 만들어진 데이터 구조이다.

Linked List에서 사용하는 Node에 이전 노드의 주소값을 가질 변수가 하나 추가된것 이외에는 동일하다.

 

출처 : https://untitledtblog.tistory.com/84

 

 

Doubly Circular LinkedList

Double Linked List를 보완하기 위하여 만들어진 데이터 구조이다.

Double Linked List에서 사용하는 Node 중 첫번째 첫번째 진입노드는 이전 노드의 주소로 끝 노드의 주소값을 가지고 있고, 끝 노드는 다음 노드의 주소로 첫번째 노드의 주소값을 가지고 있다.

 

 

ArrayList와 LinkedList의 차이

• 순차적으로 데이터를 읽기, 추가, 삭제시 ArrayList가 빠름
• 중간 위치에 데이터 삽입, 삭제시 LinkedList가 빠름
• 데이터가 많아 질수록 LinkedList는 데이터의 읽기가 평균적으로 떨어지지만 ArrayList는 index로 바로 접근하기에 상관없다.