배열, ArrayList, LinkedList를 비교분석 & HashTable

# 이 글은 싸이월드 블로그에 내가 작성했던 글을 옮겨온 글이다. #

 

 

1. 정의 : 데이터 타입이 모두 같고, 사용하는 목적도 비슷하다면 모든 데이터를 한 곳에 저장해두고 하나의 변수를 가지고 사용하는 것을 말한다. 배열에는 1차원배열과 다차원 배열이 있다.

2. 배열의 특징
① 둘이상의 변수를 선언하는 효과를 지닌다.
② 많은 양의 데이터를 일괄적으로 처리해야 하는 경우에 유용하다.
③ 지역적 특성을 지닐 수 있고, 전역적 특성을 지닐 수도 있다.

3. 배열 선언, 생성, 이용
(1) 배열의 선언 : 배열도 변수처럼 선언을 해야 사용할 수 있다.
형식 - 타입 식별자[]; ( 예: int arr[]; )

(2) 배열의 생성 : 자바에서는 배열을 생성해서 배열 변수에 대입해야 한다.
형식 - new 타입[크기]; ( 예: arr = new int[10]; )

(3) 배열 이용 : 배열을 생성해서 배열 변수에 대입히가 난 다음에 배열을 사용할 수 있다.
형식 - 배열이름[인덱스]; ( 예: arr[0] = 12; )

4. 배열을 생성해야 하는 이유 : 자바에서는 프리미티브 타입의 변수를 선언하면 그와 동시에 데이터를 젖아할 수 있는 메모리가 확보된다. 그렇기 때문에 프리미티브 타입의 변수를 선언하고 나서 바로 값을 대입할 수 있다. 하지만 배열 변수의 경우에는 선언을 해도 배열 항목을 위한 메모리가 확보되지 않는다. 그 대신 단 하나의 값을 저장할 수 있는 메모리가 확보되는데 그 메모리도 배열 항목을 위한 메모리가 아니기 때문에 배열 항목의 메모리를 확보하는 일은 따로 해야한다. 그 일이 배열의 생성식이다. 배열 변수를 선언할 때 확보했던 메모리는 배열 생성식의 결과를 담는데 사용된다.

<ArrayList>

1. 정의 :

2. ArrayList 특징 (처리하는 데이터의 갯수가 변하지 않는 경우 사용)
① 자료의 내부적인 자동 동기화 기능이 없다.
② 내부적으로 자료를 배열구조로 가지고 있는 객체로 데이터의 추가/삭제를 위해 내부적 임시배열을 작성 후 데이터를 복사
하는 방법을 사용한다.
③ 레퍼런스 타입의 데이터만 저장할 수 있다.
④ 데이터 내용의 중복이 가능하다. null값을 허용한다.
⑤ 단점 : 대량의 자료를 추가/삭제하는 경우에 내부적인 처리량이 늘어나서 상당한 성능저하를 가져온다.
⑥ 장점 : 각 데이터의 인덱스를 가지고 있기 때문에, 필요한 데이터의 접근이 한번만에 가능하다. 많은 데이터를 한 번에 다
가져와서 여러번 참조해 쓸 때 최상의 성능을 나타낸다.

3. ArrayList 선언, 생성, 이용

(1) 선언 : 리스트에 저장할 데이터의 타입을 정한다.

(2) 생성 타입 파라미터를 정했으면 ArrayList객체를 생성한다. 클래스 이름 뒤에 꺽쇠 괄호를 쓰고, 그 안에 타입파라미터를 쓴다.
ArrayList<String> list = new ArrayList<String>();

(3) 이용
① add 메서드 : 데이터 추가 ( 예 : list.add("포도")'; )
② get 메서드 : 데이터를 가져오는 것 ( 예 : String str = list.get(2); )
③ size 메서드 : 데이터의 수를 알아내는 것 ( 예 : int num = list.size(); )

4. ArrayList 데이터를 삽입/ 수정/ 삭제하는 방법

(1) add : 데이터 삽입 ( 예 : list.add(2,"키위"); )

(2) set : 데이터 수정 ( 예 : list.set(0, "오렌지"); )

(3) remove : 데이터 삭제 ( 예 : list.remove(1); )

5. ArrayList 데이터를 검색하는 방법

(1) i-dexOf : 검색할 데이터와 똑같은 값의 데이터를 파라미터로 넘겨주면 리스트에서 똑같은 값을 갖는 첫번째 데이터를 찾아서
그 위치의 인덱스를 리턴한다. ( 예 : int index = list.i-dexOf("사과"); )

<LinkedList>

1. 정의 :

2. LinkedList 특징 (처리하는 데이터의 갯수가 변하는 경우 사용)

① 다음에 나올 자료의 위치정보만 가지고 있고, 내부적인 인덱스는 가지고 있지 않다.
② 단점 : 데이터가 많은 경우의 검색 시 처음 자료로 부터 순차적으로 찾아 나가야하기 떄문에 성능이 저하된다.
③ 장점 : 데이터의 추가/삭제는 위치정보의 수정만으로 가능하기 때문에 정보의 추가/삭제 처리가 필요할 때 유용하다.

3. LinkedList 선언, 생성, 이용

(1) 선언 : 리스트에 저장할 데이터의 타입을 정한다.

(2) 생성타입 파라미터를 정했으면 LinkedList객체를 생성한다. 클래스 이름 뒤에 꺽쇠괄호를 쓰고, 그 안에 타입파라미터를 쓴다.
LinkedList <String> list = new LinkedList<String>();

(3) 이용
① add 메서드 : 데이터 추가 ( 예 : list.add("포도")'; )
② get 메서드 : 데이터를 검색 ( 예 : String str = list.get(2); )
③ size 메서드 : 데이터의 수를 알아내는 것 ( 예 : int num = list.size(); )


4. LinkedList 데이터를 삽입/ 수정/ 삭제하는 방법

(1) add : 데이터 삽입 ( 예 : list.add(2,"키위"); )

(2) set : 데이터 수정 ( 예 : list.set(0, "오렌지"); )

(3) remove : 데이터 삭제 ( 예 : list.remove(1); )

5. LinkedList 데이터의 순차 접근

(1) Iterator : Iterator 타입의 객체를 리턴하는 메서드
Iterator<String> iterator = list.iterator();

(2) next : next라는 메서드를 호출해서 LinkedList의 데이터를 순서대로 읽어올수 있다. Iterator를 통해 데이터를 읽어오는 메서드
String str = iterator.next();

6. LinkedList 스택/ 큐로 사용하는 방법

(1) 스택(stack) : 리스트처럼 일차원적으로 데이터를 저장하는 자료구조로 가장 나중에 넣었던 데이터를 가장 먼저 꺼내는 LIFO
방식을 사용한다.
LinkedList <String> stack = new LinkedList<String>();

① addLast : 스택의아래쪽으로 부터 순서대로 저장 ( 예 : list.addLast(new Integer(12); )
② removeLast : 스택의 제일 위에 있는 데이터를 가져오면서 스택에 데이터를 제거 ( 예 : Integer obj = removeLast(); )
③ getLast : 스택의 제일 위에 있는 데이터를 가져오면서 스택에 데이터를 제거하지 않는다. ( 예 : Integer obj = getLast(); )

(2) 큐( queue) : 가장 처음 넣었던 데이터를 가장 먼저 꺼내는 FIFO 입출력 방식을 사용한다.
LinkedList <String> queue = new LinkedList<String>();

① offer : 파라미터로 넘겨준 데이터를 큐에 저장( 예 : queue.offer("토끼"); )
② poll : 큐에 저장된 데이터 중 제일 앞에 있는 데이터를 가져오면서 큐에 데이터를 제거한다.( 예 : str = queue.poll(); )
③ peek: 큐에 저장된 데이터 중 제일 앞에 있는 데이터를 가져오면서 큐에 데이터를 제거하지 않는다.
( 예 : str = queue.peekt(); )


<HashTable>

1. 정의 : 여러 개의 통에 번호를 붙여놓고, 키 값을 이용하여 데이터가 들어갈 통 번호를 계산하는 자료구조이다.

2. HashMap 클래스의 사용 방법

(1) 해쉬 테이블에 저장할 데이터 타입과, 키 타입 두 가지 데이터 타입을 정해야 한다.

(2) 타입들을 이용해 HashMap 객체를 생성한다.
형식 - HashMap<키의타입, 데이터의 타입> 해쉬테이블 이름 = new HashMap<키의 타입, 데이터의 타입>();
( 예 : HashMap<String, Integer> hashtable = new hashmap<String, Integer>(); )

3. HashMap 사용

(1) put : HashMap에 데이터를 저장 할 때 사용한다. (예 : hashtable.put("해리", new Integer(95)); )

(2) get : 해쉬테이블에 저장된 데이터를 읽어오기 위해 사용한다. ( 예 : Integer num = hashtable.get("해리"); )

(3) remove : 해쉬테이블에 있는 데이터를 삭제 할 때 사용한다. ( 예 : hashtable.remove("해리"); )

4. HashMap 클래스가 해쉬 테이블의 통번호를 계산하는 방법 : hashCode 메서드를 사용

5. HashSet 클래스의 사용방법

(1) 해쉬 테이블에 저장할 데이터 타입과, 키 타입 두 가지 데이터 타입을 정해야 한다.

(2) 타입들을 이용해 HashSet 객체를 생성한다.
형식 - HashSet<키의타입, 데이터의 타입> 해쉬테이블 이름 = new HashSet<키의 타입, 데이터의 타입>();
( 예 : HashSet<String, Integer> set = new hashset<String, Integer>(); )

6. HashSet 사용

(1) add: HashSet에 데이터를 저장 할 때 사용한다. (예 : set.add("자바"); )

(2) size : HashSet에 있는 데이터의 수를 알고 싶을 때 사용한다. ( 예 : int num = set.size(); )

(3) contains : 집합에 특정 데이터가 있는지 확인할 떄 사용한다.

(4) remove : 특정 데이터를 삭제할 때 사용한다.

(5) clear : 집합에 있는 모든데이터를 삭제하고 집합을 비운다.

* 정리*

종류	특징
ArrayList	배열 기반, 데이터의 추가와 삭제 유용하지 못함, 순차적인 추가 삭제는 제일 빠름, 인덱스가 있어 임의의 요소에 대한 접근성이 뛰어남.
LinkedList	연결 기반, 데이터의 추가와 삭제에 유용함, 임의의 요소에 대한 접근성이 좋지 못함.
HashMap	배열과 연결이 결합된 형태, 추가, 삭제, 검색, 접근성이 모두 뛰어남, 검색에는 최고 성능을 보인다.
HashSet	HashMap을 이용해서 구현