자료구조 - 배열 , 리스트, 벡터

배열

연속적인 메모리 공간에 값이 채워져 있는 자료구조이다.

 

1. 인덱스를 통해 값 참조가능
2. 새로운 값 삽입/특정 인덱스값 삭제 어려움
   • 삽입/삭제시 해당 인덱스 주변 값 이동과정 필요
3. 배열 선언시 크기 지정 가능 (최초 길이 수정 불가)
   • 배열 요소 초기화시 길이는 필수이다
   • int[ ] a = new int[ ] { }; 와 같이 배열 선언시 빈 배열로 길이를 지정하지 않는다면
     배열 초기화 (삽입) 시 길이가 지정된 새 배열 인스턴스로 a 배열을 초기화 해야한다.
     → a = new int [n];
4. 간단한 구조 이므로 코딩테스트에서 주로 사용된다.

 

배열 삽입

 

배열 삭제

 

배열에서 요소를 삭제하더라도 배열의 길이는 줄어들지 않는다.
(삽입과 삭제한 요소의 갯수만큼 줄어든 길이만큼의 배열을 새로 생성해서 삭제된 이후 요소를 복사 해야 한다.)

리스트(LinkedList)

값과 포인터를 묶은 '노드' 라는 공간을 포인터로 연결한 자료구조이다.

 

 

노드란?
컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위이다.

 

 

리스트 구조  (첫번째 요소의 포인터는 HEAD, 두번째 요소의 포인터는 TAIL)

 

위 리스트 구조의 그림과 같이 포인터(NEXT)를 통해 다음 노드를 가리킨다.

 

리스트(Linked) 특징

1. 인덱스가 없으므로 요소 접근 시 HEAD 포인터 부터 순차적으로 접근한다.
   
   • 배열보다 접근속도가 느림
     (HEAD 부터 원하는 노드까지 순차적으로 포인트를 통해 접근하기 때문)
2. 포인터 연결로 인해 배열에 비해 데이터 삽입 / 삭제가 빠르다
   • 삽입
     40 → 50 사이에 30을 추가할 경우 기존 포인터 →  제거 후 40 → 30 → 50 과 같이 연결을 변경하는 형태로 삽입
   • 삭제
      40 → 30 → 50 에서 30을 제거할때 삽입과 같이 30에 연결된 모든 포인터를 제거하고 40 → 50 형태로 연결 변경
3. 가변적인 길이를 갖는다. 다시말해, 선언시 크기 지정 불필요하다.
   • 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
4. 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

 

ArrayList

미완성...

 

코딩테스트에서 배열과 리스트 두 자료구조 중에서 어떤것을 사용할지 선택하는 기준

배열

1. 크기가 고정되는 연산의 경우 
2. 데이터에 접근하는 경우가 많은 경우 

리스트 ( ArrayList or LinkedList )

1. 크기가 변할 경우
2. 데이터 삽입 삭제가 많은 경우

---

Vector

기존 배열과 같은 특징을 가지며, 배열의 단점을 보완한 동적 배열의 형태의 자료구조이다.

중간에 데이터를 삽입할 수 있으며, 가변 길이를 갖는 ArrayList의 특징을 가지고 있다.

 

1. 동적으로 원소 추가 가능 (크기가 가변적으로 자동으로 늘었다 줄었다 함.)
2. 중간데이터 삽입/삭제시 입출력이 잦으면 속도 성능 이슈가 있다.
   중간 데이터 삽입/삭제시 이전 혹은 다음 요소가 입출력 대상 요소의 앞/뒤로 이동해야 하므로 
   (마지막 위치에 데이터 삽입/삭제는 문제없음)
3. 배열과 마찬가지로 인덱스를 이용하여 데이터 요소에 접근 가능

즉, 배열에 동적 입출력 기능을 추가한 ArrayList와 같다고 보면  된다.

 

[자바 기본 선언 코드 예시]

/* 크기를 지정하지 않은 기본 인스턴스 저장 */
Vector<Object> initVector = new Vector<>();

/* 크기를 10으로 지정한 기본 인스턴스 저장 */
Vector<Object> sizeInitVector = new Vector<>(10);

/* 초기값 지정하면서 기본 인스턴스를 저장 */
Vector<Integer> valueInitVector = new Vector<>(Arrays.asList(1,2,3,4));

 

메소드 구성 또한 자바의 ArrayList와 유사하다.

 

ArrayList와 Vector의 주요 차이점

자료구조 \ 특징	동기화	스레드 안전	성능	인덱스 초과 크기 증가
ArrayList	O	O	빠름	100% 증가
Vecotor	X	X	느림	50% 증가

1. 동기화
   
   • Vector : 한번에 하나의 스레드만 접근 가능
   • ArrayList : 동시에 여러개의 스레드 작업
     (여러 스레드가 동시에 액세스 하는 경우 명시적으로 동기화 코드 추가 해야함)
2. 스레드 안전(Thread Safety)
   • Vector : 동기화 되어 있기 때문에 한번에 하나의 스레드만 접근 가능하므로 스레드 안전
   • ArrayList : 동기화 되지 않았기 때문에 명시적으로 동기화 해야 안전해진다.
3. 성능
   • ArrayList > Vector
     ArrayList는 동기화 되지 않았으므로 Vector보다 빠르다
4. 크기 증가
   • 두 자료구조 모두 동적 배열 클래스로 최대 인덱스 초과시 인덱스가 추가된다
     그러나 추가되는 수가 다르다
     • Vector : 현재 배열 크기의 100% 만큼 증가 (2배)
     • ArrayList : 현재 배열 크기의 50%만큼 증가 (1.5배)

결론

멀티스레드 환경인 경우 Vector를, 멀티 스레드 환경이 아닌 경우 ArrayList를 사용하는 것이 바람직하다.

코딩테스트의 경우 문제유형이 Vector를 사용해야 하는 명시적 요구 사항이 없는 경우 ArrayList를 사용한다.