[JAVA/자료구조] List, LinkedList, ArrayList

Interface List<E> 공식 문서
https://docs.oracle.com/javase/8/docs/api/java/util/List.html

 

List

List는 Array(배열)와 비슷한 자료구조이다.

그런데 배열에는 몇 가지 단점들이 있다.

배열은 미리 크기를 지정하여 그 공간을 확보해 놓고 사용해야 하고,  그 크기를 변경할 수 없다.

이 크기를 조절할 수 없는 것이 가장 큰 단점이다.

그래서 List를 사용한다. List는 생성할 때 크기를 지정하지 않고, 값이 추가될 때마다 List의 크기가 커진다.

---

LinkedList와 ArrayList

List는 일반적으로 LinkedList, ArrayList를 사용한다. LinkedList와 ArrayList는 구조적으로 차이가 있다.

우선 LinkedList의 자료는 메모리 상에 연달아 존재하지 않는다. 각각의 자료가 존재하는 랜덤 한 위치들을 link로 연결해 둔다. 반면, ArrayList는 배열처럼 데이터들이 순서대로 쭉 늘어서서 존재한다. 그러나 배열과 다르게 데이터를 추가, 삭제할 때마다 크기가 변경된다. 따라서 배열보다 유연하게 자료를 인덱스로 관리할 수 있다.

---

LinkedList의 삽입, 삭제

---

ArrayList의 삽입, 삭제

삭제 후 [5]번 인덱스는 없어진다.

---

시간복잡도

삽입, 삭제

이러한 구조 때문에 LinkedList는 데이터의 위치에 관계없이 삽입, 삭제를 O(1)의 시간복잡도로 빠르게 수행할 수 있다. 원하는 위치의 link만 변경해 주면 되기 때문이다. 그러나 ArrayList는 삽입, 삭제 시 O(n)의 시간복잡도가 필요하다. 배열과 같이 원하는 위치를 비우기 위해 원하는 위치오른쪽의 모든 자료를 한 칸씩 미뤄야 하기 때문이다.

조회

반대로 조회는 ArrayList가 O(1)의 시간복잡도를, LinkedList가 O(n)의 시간복잡도를 갖는다. ArrayList는 인덱스로 바로 원하는 데이터에 접근할 수 있지만, LinkedList는 원하는 데이터에 접근하려면 순차적으로 link를 따라서 접근해야 하기 때문이다.

---

LinkedList  vs  ArrayList  요약

LinkedList

• 한나의 Node는 다른 Node에 대한 참조만 가지고 있고, link로 연결되어 있다.
• 하나의 Node에 대한 link만 변경하면 되기 때문에 삽입, 삭제가 빠르다. O(1) 
• 순차 접근(Sequential Access) : 하나의 요소에 접근하려면 그전까지의 모든 link를 통해서 순차적으로 접근해야 하기 때문에 조회가 느리다. O(n)

---

ArrayList

• 배열과 같이 순차적으로 존재한다. 따라서 메모리상에 연속적인 공간이 필요하다.
• 배열과 같이 삽입, 삭제 시 다른 데이터들을 모두 움직여야 하기 때문에 느리다. O(n)
• 임의 접근(Random Access) : 배열과 같이 인덱스 값으로 바로 접근할 수 있기 때문에 조회가 빠르다. O(1)
• 맨 뒤에 데이터를 삽입하는 경우에는 당연히 O(1)의 시간복잡도를 가지지만, 배열과 같이 연속된 메모리 공간을 차지하기 때문에 삽입해야 하는 위치에 공간이 없다면 다른 공간으로 모든 데이터를 이동해야하기 때문에 O(n)의 시간복잡도를 가진다.
• 즉, ArrayList는 크기를 동적으로 늘릴 수 있는 배열(Array)이라고 보면 될 것 같다.

 

따라서 조회를 많이 하는 경우에는 ArrayList를,

삽입과 삭제를 많이 하는 경우에는 LinkedList를 사용하는 것이 좋겠다.

---

생성

ArrayList와 LinkedList 모두 List 인터페이스를 구현한 클래스이기 때문에 아래처럼 List로 선언할 수 있다.

List<Integer> list = new ArrayList<>(); // List를 구현한 ArrayList

LinkedList<Integer> list = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();

생성과 동시에 값 대입

List<Integer> list = new ArrayList(Arrays.asList(1, 2, 3));

---

Methods

값 추가, 삭제

• add() : 값 추가
• add(index, element) : index 위치에 element를 넣어줌
• addFirst() : 첫 번째에 값 추가
• addLast() : 마지막에 값 추가
• remove(index) : index 위치의 값 삭제
• remove(int num) : num 값 삭제

list.add(1);//[1]
list.add(2);//[1,2]
list.add(1, 1);//[1,2,1]
list.addFirst(5);//[5,1,2,1]
list.addLast(6);//[5,1,2,1,6]

list.remove(4);//[5,1,2,1]
list.remove(Integer.valueOf(2));//[5,1,1]

---

값 확인

• get() : index의 값을 불러온다.
• contains() : 값이 존재하는지 확인
• indexOf() : 값의 처음으로 존재하는 인덱스 확인
• lastIndexOf() : 값의 처음으로 존재하는 인덱스 확인
• size() : 사이즈 확인

//[5,1,2,1]
//get()
System.out.println(list.get(2));//결과 : 2
//contains()
System.out.println(list.contains(5));//결과 : true
//indexOf()
System.out.println(list.indexOf(1));//결과 : 1
//lastIndexOf()
System.out.println(list.lastIndexOf(1));//결과 : 3
//size()
System.out.println(list.size());//결과 : 4

---

기타 메서드

• clear() : 모든 값 삭제
• isEmpty() : 비어있는지 확인
• Collections.sort(list) : 정렬

//clear()
list.clear();

//isEmpty() : 비어있으면 true
System.out.println(list.isEmpty());

Collections.sort(list);

---

List ↔ Array 변환

(String) array -> list로 변환

• Arrays.asList()

// [A, B. C]
String[] arr = {"A","B","C"};
List<String> list = Arrays.asList(arr);

(String) list -> array 변환

list.toArray(new String [list.size()]);

// [A, B. C]
List<String> list1 = new LinkedList<>();
list1.add("A");
list1.add("B");
list1.add("C");

String[] arr = list.toArray(new String[list1.size()]);
System.out.println(Arrays.toString(arr));

---

(Integer) list -> 배열 변환

// [1,2,3]
List<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

int[] intArr = new int[list.size()];
for(int i=0;i<list.size();i++){
	intArr[i]=list.get(i).intValue();
}

int[] arr = list.stream().mapToInt(Integer ->Integer).toArray();