List - ArrayList, LinkedList

1. ADT 관점에서의 List

• 값을 저장하는 추상 자료형
• 순서가 있다.
• 중복을 허용한다.
• Set, Map을 쓰는 것이 더 적절한 상황이 아니라면 웬만해서는 List를 사용한다.

 

2. List 구현

(1) Array List

출처: https://www.javatpoint.com/arraylist-implementation-in-java

• Array 형태로 List를 구현한다.
• 기존 배열의 크기가 다 찼는데 새로운 값을 넣으려고 하면 기존 배열보다 큰 크기의 배열을 만든 후 기존 배열에 있던 값을 새로운 배열에 복사한다. 그리고 새로운 배열에 새로운 값을 집어넣는다.     
• 데이터를 삭제하려면 일단 데이터가 List 안에 있는지 탐색하는데 시간이 1차적으로 걸리고, 데이터가 만약 있다면 해당 자리에 있던 데이터를 지우고 또 data shift가 일어나므로 시간이 2차적으로 소요된다. 
• Array List 안에 있는 값을 탐색하려고 할 때 인덱스로 바로 접근해서 데이터를 찾아내는 것이 가능하다.
• 원래 값이 있던 자리에 새로운 값을 넣으려면 data shift가 필요하기 때문에 그만큼 시간이 소요된다.

 

(2) Linked List

출처: https://www.geeksforgeeks.org/what-is-linked-list/

• 각 노드들이 연결되어 있는 형태로 List가 구현된다.
• 다음 노드들을 가리키는 포인터가 노드에 붙어있다.
• 제일 첫번째 노드를 Head, 가장 마지막 노드를 Tail이라고 한다.
• 데이터는 메모리상에 비연속적으로 저장된다. 어차피 다음 노드를 가리키는 포인터가 다음 노드가 저장될 레퍼런스를 가리키고 있기 때문이다.
• 값을 탐색할 때 Head에서부터 순차적으로 탐색해야하므로 시간이 오래 걸린다.
• 새로운 값을 추가할 때 새로운 노드만 하나 만들고 이전 노드와 연결만 시켜주면 된다. (배열을 통째로 새로 만들어 줄 필요가 없다.)
• 특정 값이 있는지 없는지 모든 노드를 다 돌아보고 나서야 값의 존재여부를 확인할 수 있다.
• 특정 값을 삭제할 때도 일단 그 값이 있는지를 찾아야 하므로 시간이 걸린다. 삭제 자체는 특정 데이터가 있는 노드만 삭제하면 되기 때문에 data shift는 발생하지 않는다. 

 

3. Array List 와 Linked List 비교

• Array List는 읽기는 접근 시간이 빠르나 데이터 추가/삭제는 느리다.
• Linked List는 읽기는 모든 노드를 탐색해야하므로 시간이 오래 걸리지만 데이터 추가/삭제 자체는 빠르다.