[CS 발표] List, ArrayList, LinkedList

1. 개요

리스트(List)는 모든 프로그래밍 언어에서 가장 유용한 자료구조 중의 하나이다.

자료구조에서 리스트는 일반적으로 연결 리스트(LinkedList, 링크드리스트)를 의미한다. 자료구조에서 리스트와 양대산맥이라고 할 수 있는 배열과 자주 비교가 되곤하는데, 기능적인 측면에서 이 둘의 가장 큰 차이점은 배열은 고정된 크기를 갖지만 리스트는 크기가 얼마든 변할 수 있다는 점이다. 배열은 할당받는 물리적인 주소값에서부터 선형으로 이어져있지만 리스트는 논리적으로 연결되어있기 때문에 삽입과 삭제가 비교적 자유롭기 때문이다.
 
 

2. List 

 

Java에서 제공하는 컬렉션 프레임워크란 객체나 데이터들을 효율적으로 관리(추가, 삭제, 검색, 저장)하기 위해서 사용하는라이브러리를 의미한다. `java.util` 패키지에 포함된 인터페이스들을 구현한 클래스들이 컬렉션 프레임워크로 사용된다.

 

다양한 컬렉션 프레임워크 중에서 리스트 List는 데이터의 중복을 허용하면서 저장 순서가 인덱스로 유지되는 컬렉션을 구현하는데 사용되는 인터페이스이다. 객체(혹은 데이터)를 저장하면 인덱스가 자동으로 부여되고 부여된 인덱스를 통해 데이터의 검색 및 삭제가 가능한 것이 특징이다.

 

리스트 인터페이스에서 공통적으로 사용 가능한 주요 메서드들은 다음과 같다.
 

따라서 List 컬렉션 인터페이스를 상속해서 구현하는 클래스는 해당 메서드들을 재정의(Override, 오버라이드) 해야한다. List 인터페이스를 구현한 클래스로는 ArrayList, Vector, Stack, LinkedList가 있다.

 

그 중에서도 ArrayList와 LinkedList에 대해서 알아보도록 하자.

 

 

3. ArrayList

 

ArrayList는 List 인터페이스를 구현한 클래스로 배열을 개선한 자료구조라고 이야기할 수 있다. 배열은 기본적으로 선언할 때 정한 크기로 고정이 되지만 Array 설정된 저장 용량(capacity)보다 많은 데이터가 들어오면 용량으로 자동으로 늘어난다.

 

C++이 익숙하다면 STL(Standard Template Library)의 vector를 생각하면 이해가 편할 것이다. 여담으로 Java에도 Vector 컬렉션 클래스가 존재하며 유사한 역할을 수행한다. 하지만 Vector는 쓰레드 간에 자동으로 동기화를 보장하기 때문에 멀티 쓰레드 환경에서 가끔 사용되고 일반적인 경우에는 속도가 더 빠른 ArrayList를 사용한다.

 

ArrayList는 배열과 마찬가지로 연속된 메모리 공간에 순차적으로 데이터를 저장하기 때문에, 배열의 index를 통해 접근하며 조회 상황에서 시간 복잡도가 O(1)로 매우 빠른 성능을 보인다. 하지만 삽입과 삭제의 경우에는 데이터 삽입 위치에 따라 오버로딩된 메서드가 작동하며 서로 다른 시간 복잡도를 갖는다.

 

ArrayList는 배열이기 때문에 중간에 값을 끼워넣는 연산은 불가능하다. 만약 새로운 값을 추가하려고 할 때 배열의 size보다 커지는 경우에 이전 크기의 2배가 되는 배열을 생성하고 기존 배열 전체를 복사한 뒤 제일 뒤에 값을 추가하기 때문에 O(n)의 시간 복잡도를 갖는다. 생성시 따로 size를 설정하지 않았다면 default size는 10이다.

 

삭제의 경우에도 중간 데이터를 삭제하고 이후의 데이터를 한 칸씩 앞으로 밀어야하기 때문에 O(n)의 시간복잡도를 지닌다.

 

4. LinkedList

 

LinkedList는 선형 자료구조 중에서도 각 노드가 데이터와 링크를 가지고 논리적으로 연결되어 있는 연결 리스트를 List 인터페이스로 구현한 클래스이다. 연결 리스트는 순차적인 데이터를 물리적으로 연속된 공간에 할당하는 것이 아니라  

 

List의 구현 클래스이므로 ArrayList나 Vector와 사용 방법은 동일하다. 하지만 구조는 다르게 구성되어 있다. 위의 컬렉션들은 인덱스로 데이터를 관리하지만 LinkedList는 인접한 곳을 링크하여 체인처럼 관리한다. LinkedList는 중간의 데이터를 삭제할 때 인접한 곳의 링크만을 변경하면 되기 때문에 중간에 데이터를 추가/삭제하는 경우 처리 속도가 빠르다. 차이점은 아래와 같다.

 

일반적인 경우

추가를 원하는 index에 도달할 때까지 순차 접근을 하는 시간복잡도 O(n)

index-1의 노드의 next와 index+1의 prev를 새로 추가한 노드에 연결하는 작업은 n에 영향을 받지않는 상수 시간이기 때문에 O(1)이다

따라서, O(n)의 시간복잡도를 가진다

 

시작이나 끝에 요소를 추가할 때

LinkedList는 head와 tail을 갖는 doubleLinkedList의 구조이기 때문에 시작과 끝에 해당하는 노드을 찾아가는데는 O(1)이라는 시간 복잡도를 갖게된다

따라서, 시간 복잡도는 O(1)이다.

 

 
 
# 참고 문헌

https://blog.naver.com/heartflow89/220989831899

[JAVA/자바] 컬렉션 프레임워크(collection framework, 자료구조) 의미 / 종류 / 차이점

https://blog.naver.com/heartflow89/220991199432

[JAVA/자바] List - ArrayList, Vector, LinkedList

https://m.blog.naver.com/cjhol2107/221759748089

[JAVA] List와 ArrayList, LinkedList의 개념, 차이

https://yeonjewon.tistory.com/39

Linked List (연결 리스트)

https://lelecoder.com/78

Java 리스트(List) 컬렉션 종류 ArrayList, Vector, LinkedList

https://pongic.tistory.com/3

[Java] 리스트 (List) 정리

https://velog.io/@bky373/Data-Structure-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4

[자료구조] 자료구조, 배열과 리스트에 대한 이해

https://adjh54.tistory.com/319

[Java/자료구조] 선형구조 - 연결 리스트 이해하기 : 단순, 이중, 순환 연결리스트

 
 
# 사진출처
https://pacientes.github.io/posts/2021/03/datastructure-compare-array-with-linked-list/
https://hwan1001.tistory.com/10
https://blog.naver.com/PostView.nhn?blogId=heartflow89&logNo=220991199432&redirect=Dlog&widgetTypeCall=true&directAccess=false

https://girawhale.tistory.com/8