자료 구조 : List
자바의 컬렉션
- Collection 인터페이스를 구현하고 있는 자료구조
- List : 순서가 있는 목록(List)형
- Set : 순서가 없는 셋(Set)형
- Queue : 먼저 들어온 것이 먼저 나가는 큐(Queue)형
- Map : 키-값(key-value)으로 저장되는 맵(Map)형
Collection 인터페이스는 어떻게 생겼을까 ?
Collection
은 Iterable<E>
이라는 인터페이스를 확장했다.
Iterable
리턴 타입 | 메소드 이름 및 매개 변수 |
---|---|
Iterator | iterator() |
Iterable 인터페이스에 선언 되어 있는 메소드는 단지 하나이다.
iterator() 라는 메소드만 Iterable 인터페이스에 선언되어 있고, 이 메소드는 Iterator라는 인터페이스를 리턴한다.
Collection
인터페이스가 Iterable
인터페이스를 확장했다는 의미는, Iterator
인터페이스를 사용하여 데이터를 순차적으로 가져올 수 있다는 의미이다.
- Collection 인터페이스에 선언된 주요 메소드들
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
boolean | add(E e) | 요소를 추가한다. |
boolean | addAll(Collection) | 매개 변수로 넘어온 컬렉션의 모든 요소를 추가한다. |
void | clear() | 컬렉션에 있는 모든 요소 데이터를 지운다. |
boolean | contains(Object) | 매개 변수로 넘어온 객체가 해당 컬렉션에 있는지 확인한다. 동일한 값이 있으면 true를 리턴한다. |
boolean | containsAll(Collection) | 매개 변수로 넘어온 객체들이 해당 컬렉션에 있는지 확인한다. 매개 변수로 넘어온 컬렉션에 있는 요소들과 동일한 값들이 모두 있으면 true를 리턴하다. |
boolean | equals(Object) | 매개 변수로 넘어온 객체와 같은 객체인지 확인한다. |
int | hashCode() | 해시 코드값을 리턴한다. |
boolean | isEmpty() | 컬렉션이 비어있는지 확인한다. 비어있으면 true를 리턴한다. |
Iterator | iterator() | 데이터를 한 건씩 처리하기 위한 Iterator 객체를 리턴한다. |
boolean | remove(Object) | 매개 변수와 동일한 객체를 삭제한다. |
boolean | removeAll(Collection) | 매개 변수로 넘어온 객체들을 해당 컬렉션에서 삭제한다. |
boolean | retainAll(Collection) | 매개 변수로 넘어온 객체들만을 컬렉션에 남겨 둔다. |
int | size() | 요소의 개수를 리턴한다. |
Object[] | toArray() | 컬렉션에 있는 데이터들을 배열로 복사한다. |
toArray(T[]) | 컬렉션에 있는 데이터들을 지정한 타입의 배열로 복사한다. |
본격적으로 List에 대해서 알아보자.
List ?
- List는 순서가 있는 자료구조이다.
- 배열과 비슷하다. 배열은 크기가 정해져 있을 때 유용하고 메모리 효율면에서도 좋다. 하지만 데이터 크기를 가늠이 안 올때 사용하기 좋다.
- List 인터페이스를 구현한 대표적인 클래스 -
ArrayList
,Vector
,Stack
,LinkedList
ArrayList와 Vector 이야기
ArrayList는 Vector와 매우 유사하다. 클래스의 사용법도 거의 동일하고 기능도 거의 유사하다.
이 두 클래스를 “확장 가능한 배열”
이라고 생각하면 된다.
Vector는 JDK 1.0에서 탄생했고, ArrayList는 JDK 1.2에서 추가되었다.
둘의 큰 차이점은 Thread 안정성에 있어서 차이가 크다.
ArrayList 객체는 여러 명이 접속하여 값을 변경하려고 하면 문제가 발생할 수 있다. 하지만 Vector는 동시에 접속하여 값을 변경하려는 문제에 있어서 안전하다.
Vector | ArrayList |
---|---|
Thread safe | Not Thread safe |
ArrayList에 대해서 더 깊게 …
컬렉션, 쓰레드, IO, 네트워크 등 관련 클래스를 사용할 때에는 그 클래스의 상속 관계를 살펴보면 좋음. → 습관화 하자.
- ArrayList 상속 관계
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.ArrayList<E>
위에서 유심히 봐야하는 것은 AbstractCollection
, AbstractList
이다.
AbstractCollection
은Collection 인터페이스
중 일부 공통적인 메소드를 구현해 놓은 것들이 있다.AbstactList
는List 인터페이스
중 일부 공통적인 메소드를 구현해 놓은 것이다.
➡️ArrayList가 구현한 모든 인터페이스
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
인터페이스 | 용도 |
---|---|
Serializable | 원격으로 객체를 전송하거나, 파일에 저장할 수 있음을 지정 |
Cloneable | Object 클래스의 clone() 메소드가 제대로 수행될 수 있음을 지정. 즉, 복제가 가능한 객체임을 의미한다. |
Iterable | 객체가 “foreach” 문자을 사용할 수 있음을 지정 |
Collection | 여러 개의 객체를 하나의 객체에 담아 처리할 때의 메소드 지정 |
List | 목록형 데이터를 처리하는 것과 관련된 메소드 지정 |
RandomAccess | 목록형 데이터에 보다 빠르게 접근할 수 있도록 임의로(random하게) 접근하는 알고리즘이 적용된다는 것을 지정 |
인터페이스들을 ArrayList가 구현했다는 것은 각 인터페이스에서 선언한 기능을 ArrayList에서 사용할 수 있다는 뜻이다.
ArrayList의 생성자
ArrayList의 생성자는 3개다.
생성자 | 설명 |
---|---|
ArrayList() | 객체를 저장할 공간이 10개인 ArrayList를 만든다. |
ArrayList(Collection<? extends E> c | 매개 변수로 넘어온 컬렉션 객체가 저장되어 있는 ArrayList를 만든다. |
ArrayList(int initialCapacity) | 매개 변수로 넘어온 initialCapacity 개수만큼의 저장 공간을 갖는 ArrayList를 만든다. |
1. 첫 번째 생성자 : ArrayList()
2. 두 번째 생성자 : ArrayList(Collection<? extends E> c
3. 세 번째 생성자 : ArrayList(int initialCapacity)
- 예시)ArrayList는 이렇게 사용하는건가? → X
list1
객체를 생성하면, 이 ArrayList에는 어떤 객체도 넣을 수 있다.
public class ListSample{
public static void main(String[] args){
ListSample sample = new ListSample();
sample.checkArrayList1();
}
public void checkArrayList1(){
ArrayList list1 = new ArrayList();
list1.add(new Object());
list1.add("ArrayListSample");
list1.add(new Double(1));
}
}
위의 예시처럼 서로 다른 종류의 객체를 하나의 배열에 넣지 않고, 한 가지 종류의 객체만 저장한다.
컬렉션 관련 클래스의 객체들을 선언할 때 제네릭을 사용하여 선언하는 것은 명확히 타입을 바로 알 수 있기 때문에 더 좋다.
ArrayList<String> list1 = new ArrayList<>();
- 제네릭을 넣어서 :
ArrayList<String> list1 = new ArrayList<>();
public void checkArrayList1() {
ArrayList<String> list1 = new ArrayList<>();
list1.add(new Object());
list1.add("ArrayListSample");
list1.add(new Double(9));
}
- 컴파일 에러가 뜬다. → 제네릭 때문에 컴파일 에러
- String 타입만 넣을 수 있는 것이다. 다른 타입은 못 들어간다.
ArrayList의 객체를 선언할 때 매개 변수를 넣지 않을 경우
- 디폴트 크기는 10이다. →
private static final
로 선언되어있음
- 10개 이상의 데이터가 들어가면 크기를 늘이는 작업이 자동으로 수행된다. 이런 작업이 수행되면 애플리케이션 성능에 영향을 준다.
ArrayList<String> list2 = new ArrayList<String>(100); // 이렇게 크기 지정
ArrayList에 데이터 추가 방법
- 추가 메소드
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
boolean | add(E e) | 매개 변수로 넘어온 데이터를 가장 끝에 담는다. |
void | add(int index, E e) | 매개 변수로 넘어온 데이터를 지정된 index 위치에 담는다. |
boolean | addAll(Collection<? extends E> c | 매개 변수로 넘어온 컬렉션 데이터를 가장 끝에 담는다. |
boolean | addAll(int index, Collection<? extedns E> c) | 매개 변수로 넘어온 컬렉션 데이터를 index를 지정된 위치부터 담는다. |
add(E e)
- 메소드를 사용하여 데이터를 추가했을 때 boolean 값은 제대로 추가 되었는지 여부를 말한다. 보통 add() 메소드를 호출하면 false가 떨어지는 경우가 거의 없다.
add(int index, E e)
- index함께 데이터를 넘겨주는 add() 메소드는 지정된 위치에 데이터를 담는다.
- 지정된 위치에 있는 기존의 데이터들은 위차가 하나씩 뒤로 밀린다.
addAll(Collection<? extends E> c)
- 예시를 통해서 알아보자.
- 우선 list를 담을 ArrayList를 만들어준다. →
ArrayList<String> list2 = new ArrayList<>();
- 결과 :
List2 = 0
List2 = A
List2 = A1
List2 = B
List2 = C
List2 = D
List2 = E
Tip.
list에 있는 내용을 addAll() 메소드를 이용해서 list2로 복사했다. → `list2.addAll(list);`
하지만 더 편리한 방법이 있다.
`생성자`를 이용하면 된다.
`ArrayList<String> list2 = new ArrayList<String>(list);`
이렇게 이용하면 더 편리하다.
이와 같이할 수 있는 이유는 ArrayList에는 Collection 인터페이스를 구현한 어떠한 클래스도 포함 시킬수 있는 생성자가 있기 때문이다.
list2를 list로 치환해버린다면 어떻게 될까?
➡️ArrayList의 shallow copy , Deep copy
- 결과
List2 A
List2 OOops
- 의문점 : 왜 Ooops는 list2에 넣지도 않았는데 왜 추가 되었을까?
list2 = list
이것은 값만 사용하는 것이 아니다. list라는 객체가 생성되어 참조되고 있는 주소
까지도 사용하겠다는 의미이다.
두 객체의 변수는 다르지만, 하나의 객체가 변경되면 다른 이름의 변수를 갖는 객체의 내용도 바뀐다.
얇은 복사(shallow)
, 깊은 복사(deep copy)
라는 개념을 알고 가야한다.
얇은 복사
는 원본 객체의 주소값만을 할당하는 것은 Shallow copy이다. 즉, 복사한 객체가 변경된다면 기존의 객체도 변경이 되는 것이다.
깊은 복사
는 객체의 모든 값을 복사하여 복제된 객체에 있는 값을 변경해도 원본에 영향이 없도록 한다.
Collection 인터페이스를 구현한 클래스의 객체에서 사용할 수 있는 for 루프의 구조
for(타입이름 임시변수명 : 반복대상객체){
}
ArrayList에서 제공하는 size()메소드
size()
메소드는 배열에서 쓰는 length()
메소드와 유사한 것처럼 보일 수 있다.
하지만 서로 다르다.
어떤점이 다를까 ?
Collection을 구현한 인터페이스는 size() 메소드를 통하여 들어가 있는 데이터의 개수를 확인한다.
String 문자열의 길이를 구하는 length() 메소드는 문자열의 길이를 가져온다. 즉, 저장 공간 개수
를 의미한다.
둘이 헷갈릴 경우가 조금씩 있다. 의식해서 하면은 헷갈리지는 않을 것 같다.
ArrayList 데이터 추출
- ArrayList 객체에 있는 값을 가져올 때 : get() 메소드 사용
- get() 메소드는 단, 한 건의 데이터를 꺼내는 메소드이다.
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
int | size() | ArrayList 객체에 들어가 있는 데이터의 개수를 리턴한다. |
E | get(int index) | 매개 변수에 지정한 위치에 있는 데이터를 리턴한다. |
int | indexOf(object o) | 매개 변수로 넘어온 객체와 동일한 데이터의 위치를 리턴한다. |
int | lastIndexOf(object o) | 매개 변수로 넘어온 객체와 동일한 마지막 데이터의 위치를 리턴한다. |
ArrayList 객체에 있는 데이터들을 배열로 뽑아내기
- toArray() 메소드를 사용하면 된다.
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
obejct[] | toArray() | ArrayList 객체에 있는 값들을 Obejct[] 타입의 배열로 만든다. |
toArray(T[] a) | ArrayList 객체에 있는 값들을 매개 변수로 넘어온 T 타입의 배열로 만든다. |
public void checkArrayList6(){
ArrayList<String> list = new ArrayList<>();
list.add("A");
String[] strList = list.toArray(new String[0]);
System.out.println(strList[0]);
}
매개 변수로 변환하려는 타입의 배열을 지정해주는 것에 new String[0]
을 유심히 보면…
ArrayList
객체의 데이터 크기가 매개 변수로 넘어간 배열 객체의 크기보다 클 경우에는 매개 변수로 배열의 모든 값이 null
로 채워진다.
public void checkArrayList7(){
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
String[] tempArray = new String[3];
String[] strList = list.toArray(tempArray);
for (String temp : strList) {
System.out.println(temp);
}
}
- 결과
A
B
C
- tempArray라는 배열의 크기를 5로 지정하고,
String[] tempArray = new String[5];
- 결과
A
B
C
null
null
- tempArray 배열의 크기를 2로 지정
String[] tempArray = new String[2];
- 결과
null
null
ArrayList 데이터 삭제
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
void | clear() | 모든 데이터를 삭제한다. |
E | remove(int index) | 매개 변수에서 지정한 위치에 있는 데이터를 삭제하고, 삭제한 데이터를 리턴한다. |
boolean | remove(Object o) | 매개 변수에 넘어온 객체와 동일한 첫 번째 데이터를 삭제한다. |
boolean | removeAll(Collection<?> c) | 매개 변수로 넘어온 컬렉션 객체에 있는 데이터와 동일한 모든 데이터를 삭제한다. |
clear()
ArrayList의 데이터들을 깨끗이 지운다.
remove()
remove() 메소드는 get() 메소드와 동일하게 지정한 위치의 데이터를 리턴하긴 하지만, 그 위치의 데이터를 지우고 리턴한다.
public void checkArrayList8(){
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("A");
System.out.println(list.remove("A"));
for (int loop = 0; loop < list.size(); loop++) {
System.out.println("list.get(" + loop + ")=" + list.get(loop));
}
}
- 결과
true
list.get(0)=B
list.get(1)=C
list.get(2)=A
“A”
값을 remove() 메소드로 삭제를 했다 그런데 앞에 있는 “A”
만 삭제되고 뒤에 있는 “A”
는 삭제가 안된걸 볼 수 있다.
removeAll()
remove()는 매개 변수로 넘어온 객체와 동일한 첫 번째 데이터만 삭제하지만, removeAll()메소드는 매개 변수로 넘어온 컬렉션에 있는 데이터와 동일한 모든 데이터를 삭제한다.
public void checkArrayList8(){
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("A");
ArrayList<String> temp = new ArrayList<>();
temp.add("A");
list.removeAll(temp);
for (int loop = 0; loop < list.size(); loop++) {
System.out.println("list.get(" + loop + ")=" + list.get(loop));
}
}
- 결과
list.get(0)=B
list.get(1)=C
ArrayList 객체에 있는 값 변경
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
E | set(int index, E element) | 지정한 위치에 있는 데이터를 두 번째 매개 변수로 넘긴 값으로 변경한다. 그리고, 해당 위치에 있던 데이터를 리턴한다. |
public void setList(){
ArrayList<String> list = new ArrayList<>();
list.add("X");
list.add("B");
list.add("C");
list.set(1, "A"); // set(int index, E element)
list.set(2, "A"); // set(int index, E element)
for (String s : list) {
System.out.println(s);
}
}
- 결과
X
A
A
trimToSize()
- ArrayList 객체 공간의 크기를 데이터의 개수만큼으로 변경한다.
- String의 trim() 메소드와 유사하다. 앞 뒤의 공백을 없애는 것
- 이 메소드는 저장할 수 있는 공간은 만들어 두었지만, 데이터가 저장되어 있지 않을 때 해당 공간을 없애버린다.
- 만약 ArrayList의 객체를 원격으로 전송하거나, 파일로 저장하는 일이 있을 때 이 메소드를 한 번 호출함으로써, 데이터의 크기를 줄일 수 있다.
public class ListSample {
public static void main(String[] args){
ArrayList<Integer> arr = new ArrayList<Integer>(9);
arr.add(2);
arr.add(4);
arr.add(5);
arr.add(6);
arr.add(11);
arr.trimToSize();
System.out.println("The List elements are:");
for (Integer number : arr) {
System.out.println("Number = " + number);
}
}
}
- 결과
The List elements are:
Number = 2
Number = 4
Number = 5
Number = 6
Number = 11
이미지 출처 : geeksforgeeks - https://www.geeksforgeeks.org/arraylist-trimtosize-java-example/?ref=gcse
Stack 클래스
LIFO(Last In First Out)는 후입선출이라고 한다. 즉, 나중에 들어온 값을 먼저 처리하는 것을 의미한다.
Stack 클래스는 잘 사용하지 않는다. 이유는 이 보다 빠른 클래스가 있기 때문이다.
바로 ArrayDeque
라는 클래스이다.
하지만 ArrayDeque는 치명적인 단점이 있다. 쓰레드에 안전하지 못하기 때문이다.
쓰레드 안전을 위한다면 Stack을 사용해야한다.
Stack을 본격적으로 알아보자.
- 상속관계
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.Vector<E>
java.util.Stack<E>
Stack의 부모 클래스는 Vector이다. 따라서 Vector 클래스에서 제공하는 모든 메소드를 사용할 수 있다.
오호 ~
Stack 클래스에서 구현한 인터페이스는 Serializable
, Cloneable
, Iterable<E>
, Collection<E>
, List<E>
, RandomAccess
로 ArrayList 클래스에서 구현한 인터페이스와 모두 동일하다…..!
- 생성자
생성자 | 설명 |
---|---|
Stack() | 아무 데이터도 없는 Stack 객체를 만든다. |
- Stack 클래스의 메소드
리턴 타입 | 메소드 이름 및 매개 변수 | 설명 |
---|---|---|
boolean | empty() | 객체가 비어있는지를 확인한다. |
E | peek() | 객체의 가장 위에 있는 데이터를 리턴한다. |
E | pop() | 객체의 가장 위에 있는 데이터를 지우고, 리턴한다. |
E | push(E item) | 매개 변수로 넘어온 데이터를 가장 위에 저장한다. |
int | search(Object o) | 매개 변수로 넘어온 데이터의 위치를 리턴한다. |
- 스택 구현
import java.util.*;
public class Main{
static int[] stack;
static int size=0 ;
public void push(int data){
stack[size] = data;
size +=1;
}
public int pop(){
if(size == 0) return -1;
else{
size--;
return stack[size];
}
}
public int top(){
if(size == 0) return -1;
return stack[size -1];
}
public int size(){
return size;
}
public int empty(){
if(size == 0) return 1; //비어있다
else return 0;// 비어있지않다.
}
public static void main(String[] args){
Main T = new Main();
Scanner in = new Scanner(System.in); //
StringBuilder sb = new StringBuilder(); //문자 입력
int n = in.nextInt(); // 데이터 입력
stack = new int[n]; //스택공간
for(int i = 0 ; i < n ; i++){ //Test : 14
String s = in.next(); // push, pop, top, size,empty
switch(s){
case "push":
T.push(in.nextInt()); //data : 1 ,2 ...etc
break;
case "pop":
sb.append(T.pop()).append('\n');
break;
case "size":
sb.append(T.size()).append('\n');
break;
case "empty":
sb.append(T.empty()).append('\n');
break;
case "top":
sb.append(T.top()).append('\n');
break;
}
}
System.out.println(sb);
}
}
ArrayList를 정리하며…
ArrayList는 정말 많이봤다. 알고리즘에서 지겹도록 나온 개념이다.
잘 쓰이는 것을 알고 더 세심히 정리하고 싶었다.
시간을 갈아 넣어 잘 한거 같으면서도 다시 읽어보면 많이 부족한 글쓰기가 보인다.
어색한 것들을 조금씩 나아지는 방법 글쓰는 습관 중 안좋은 습관들이 조금 널려있다.
조금씩 찾아서 의식적으로 고쳐나가자…