[F-Lab 챌린지 5일차] TIL : 자바의신 22장 - List

성수데브리·2023년 7월 3일
0

f-lab_java

목록 보기
4/73

[F-Lab 챌린지] TIL : 자바의신 22장 - List

학습 목표

  • 자바 컬렉션

학습 결과 요약

  • Collection 인터페이스 확장 인터페이스는 List, Queue, Set 있다.
  • List 는 데이터를 담을 때 순서를 보장하는 자료구조다. 대표적 구현 클래스는 ArrayList 가 있는데 내부적으로 배열을 사용해 데이터를 추가한다. 배열이 다 차면 동적으로 더 큰 용량의 배열을 생성해 기존 데이터를 복사한다.
  • Queue 는 LIFO 구조로 동작을 보장하는 자료구조. 요소에 접근할 때 sequential access 한다. AbstractSequentialList 와 Deque 를 상속, 구현한 LinkedList 구현 클래스가 대표적이다.
  • Set 은 데이터의 중복 처리를 할 때 유용한 자료구조 대표적 구현 클래스는 HashSet 가 있다. 내부적으로 HashMap 을 사용하는데 Key-Value 쌍에서 Key 에 요소를 담고 Value 는 더미 객체를 저장한다.

학습 내용

자바 컬렉션

  • 자바에서 목록성 데이터를 처리하는 자료 구조를 통칭한다.
  • 자료구조란 여러 데이터를 담을 때 사용한다. 자료구조 유형
    1. 순서가 있는 List 형
    2. 순서가 중요하지 않은 set 형
    3. LIFO - Queue 형
    4. Key-Value 쌍으로 저장되는 Map형

Collection

https://www.javaguides.net/p/java-collections-tutorial.html

https://www.javaguides.net/p/java-collections-tutorial.html

  • 자바의 자료구조에서 List, Set, Queue 형의 자료구조는 Collection 인터페이스를 구현한다.

  • 여러 객체를 하나의 객체에 담아 처리할 때 공통적으로 사용되는 여러 메서드들을 선언해 놓았다.

  • 기능

    Collection (Java Platform SE 8 )

    Collection 인터페이스 기능은 위 문서에 명시되어 있다.

    1. Query Operations
      1. contains, containsAll
    2. Modification Operations
      1. add, addAll, clear, remove, removeAll, retainAll
    3. Comparison and hashing

List

  • List 인터페이스는 Collection 를 확장하였다.
    public interface List<E> extends Collection<E> { // 생략 }
  • List 의 특징은 자료에 순서가 있다는 것이다.

    An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

    List 는 원소가 삽입되는 위치를 제어할 수 있다. 검색이나 읽기 연산에서 index(목록 내 위치) 를 사용한다.
  • 원소의 중복 허용
    • Set 과 달리 목록에 중복된 원소를 추가할 수 있다.
  • List 인터페이스에는 iterator, add, remove, equals, and hashCode 메서드에 Collection 인터페이스에 지정된 것 외에 추가 규칙을을 명시했다.
    • add(*E* e)

      Ensures that this collection contains the specified element (optional operation). Returns true if this collection changed as a result of the call. (Returns false if this collection does not permit duplicates and already contains the specified element.)

      Collection 인터페이스의 add(E e) 는 목록에 매개변수로 받은 원소가 추가가 되면 true를 리턴하도록 구현할 것을 명시했다.

      Appends the specified element to the end of this list (optional operation).

      List 인터페이스에 선언된 add(E e) 은 목록의 맨 끝에 요소를 추가할 것을 명시하고 있다.
    • remove(*Object* o)

      Removes the first occurrence of the specified element from this list, if it is present (optional operation)

      List 는 중복이 허용되기 때문에 요소 삭제는 목록에서 첫번째로 검색된 요소를 삭제한다.
    • equals(Object o)

      Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if Objects.equals(e1, e2).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface.

      List 구현 클래스 객체의 equals() 재정의는 두 List 객체가 같은 순서의 같은 객체를 가졌을 경우 동등하다고 판단하도록 명시되어있다.
  • View 전용 객체를 리턴하는 static 메서드들이 있는데 모두 내부적으로 List 변경이 불가능한 객체를 생성해서 리턴해준다. Shot_20230702_213801.png

ArrayList

  • 목록에 있는 데이터의 순서가 중요할 때 사용한다.
  • ArrayList는 List 의 구현클래스다.
    public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • ArrayList 의 특징은 확장 가능한 배열이다.
  • 내부적으로 배열을 갖고 있다. 배열의 크기는 고정적이기 때문에 이 배열이 다 차면 터 큰 배열을 새로 할당한 다음 기존 값을 복사한다.
  • Vector 와 거의 동일하지만 차이점은 thread-safe 하지 않다.
  • 클래스 멤버 살펴보기
    /**
	 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
   * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
	 * Shared empty array instance used for default sized empty instances. We
	 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
	 * first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    • 기본 용량은 10이다
    • 빈 배열을 static 으로 생성해놓고 빈 배열을 할당할 때마다 재사용 하고 있다.
  • 인스턴스 멤버 살펴보기 transient 키워드는 직렬화 시 제외할 멤버일 경우 선언한다 실제 원소를 보관하는 배열 타입의 참조변수가 선언되어 있다.
    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    배열의 크기가 아닌 요소의 개수를 저장하는 변수다
    /**
	 * The size of the ArrayList (the number of elements it contains).
	 *
	 * @serial
 */
private int size;
    객체가 관리하는 배열의 크기가 변경된 횟수를 저장한다. 
    protected transient int modCount = 0;
  • 생성자 생성자에는 3가지가 있다.

    1. 초기화 시 배열의 크기를 지정할 수 있는 생성자

      /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
  public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {
          this.elementData = EMPTY_ELEMENTDATA;
      } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }

    2. 기본 생성자 : 디폴트 용량으로 배열의 크기가 초기화 된다.

      
/**
	 * Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

    3. Collection 타입을 매개변수로 받는 생성자

        /**
   * Constructs a list containing the elements of the specified
   * collection, in the order they are returned by the collection's
   * iterator.
   *
   * @param c the collection whose elements are to be placed into this list
   * @throws NullPointerException if the specified collection is null
   */
  public ArrayList(Collection<? extends E> c) {
      Object[] a = c.toArray();
      if ((size = a.length) != 0) {
          if (c.getClass() == ArrayList.class) {
              elementData = a;
          } else {
              elementData = Arrays.copyOf(a, size, Object[].class);
          }
      } else {
          // replace with empty array.
          elementData = EMPTY_ELEMENTDATA;
      }
  }
  • 어떻게 배열의 용량을 조절할까?

  1. 원소가 추가될 때마다 modCount를 1 증가한다.

  2. add 내부에서 호출되는 add 헬퍼 메서드에서 용량 증가를 처리한다. 

    ArrayList<Integer> intList = new ArrayList<>();
intList.add(1);
    public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

  3. 인스턴스 필드 elementData 배열의 길이가 배열의 길이를 저장하는 size 변수와 같을 때 배열의 크기를 증가시킨다.

    Arrays.copyOf() 을 사용해 증가된 크기의 배열을 생성한 후 기존 배열의 원소를 복사한다.

    /**
 * This helper method split out from add(E) to keep method
 * bytecode size under 35 (the -XX:MaxInlineSize default value),
 * which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 * @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

  4. 증가시킬 배열의 크기를 계산하는 방법

    grow factor 는 기존 배열 사이즈의 1.5 다.

    ArrayList 에 요소를 하나씩 추가하면 grow() 가 더 많이 호출된다고 한다. 아직 이해 못했음. 

    /**
	 * Returns a capacity at least as large as the given minimum capacity.
	 * Returns the current capacity increased by 50% if that suffices.
	 * Will not return a capacity greater than MAX_ARRAY_SIZE unless
	 * the given minimum capacity is greater than MAX_ARRAY_SIZE.
	 *
	 * @param minCapacity the desired minimum capacity
	 * @throws OutOfMemoryError if minCapacity is less than zero
*/
private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

  • ArrayList 는 마커 인터페이스 Cloneable 을 구현함

    ArrayList 클래스에 재정의된 clone 은 shallow copy 를 한다.

    복사 시 배열의 원소는 복제된 객체가 아닌 단순히 참조값을 복사한다. 

    /**
     * Returns a shallow copy of this {@code ArrayList} instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this {@code ArrayList} instance
     */
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    ArrayList<Mock> strList = new ArrayList<>();

Mock bmw = new Mock("BMW");
strList.add(bmw);

ArrayList<Mock> copyList = (ArrayList<Mock>) strList.clone();

bmw.setName("BMW -> Porsche");

System.out.println("strList = " + strList);
System.out.println("copyList = " + copyList);

-----------출력 결과-----------

strList = [Mock{name='BMW -> Porsche'}]
copyList = [Mock{name='BMW -> Porsche'}]

    그래서 복재된 리스트 요소 객체들에 변경을 해도 영향을 받지 않으려면 Deep Copy 를 해야 하는데,

    자바의 신에서는 생성자를 사용하거나 addAll() 메서드를 사용할 것을 권장하고 있다.

  • RandomAccess marker interface

    	![](https://velog.velcdn.com/images/gutenlee/post/7d3a330a-6a2e-4454-986c-624459d5c84d/image.png)

    Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

    RandomAccess 마커 인터페이스를 구현하면 random access 가 빠르게 동작할 수 있도록 최적의 알고리즘을 적용해야 한다.

Vector

Vector 클래스는 ArrayList 와 거의 유사하지만 차이점은 주요 기능 메서드들에 synchronized 키워드가 선언되어있다. ArrayList 와 달리 thread-safe 를 보장한다.

Stack

Stack 은 Vector 를 상속한다. Vector 가 LIFO (last-in-first-out) 로 구조로 동작하도록 구현되어 있다.

또한 synchronized 선언되어 있어 thread-safe 를 보장한다.

public class Stack<E> extends Vector<E> {}

Stack 은 상속을 잘못 받은 사례다.

LIFO 구조로 동작하는 의도와는 달리 Vector 를 상속하면서 Vector 의 set() , remove() 메서드 호출이 가능해 중간 index 위치에 데이터 삽입, 삭제가 가능하다. 

Stack<String> stacks = new Stack<>();
stacks.push("A");
stacks.push("B");

stacks.set(1, "C"); // Vector 의 메서드 호출

Stack 클래스 주석에서도 완전한 LIFO 스택 연산을 사용하려면 ArrayDeque 클래스 사용을 권장하고 있다.

예시

참고

profile
성수데브리
개발자
이전 포스트

[F-Lab 챌린지 4일차] TIL : 자바의신 21 장 - 제네릭

다음 포스트

[F-Lab 챌린지 6일차] TIL : 자바의신 23장 - Set & Queue

0개의 댓글