[리스트] 배열 리스트와 연결 리스트

생활 속 리스트 예시

• 위시 리스트, 블랙 리스트, 서비스를 기다리는 사람 리스트 

 

리스트 자료구조의 ADT(추상 데이터 타입)

리스트의 기본 정의

• 줄 세워져 있는 데이터

 

ADT

i번째 자리에 원소 x를 삽입한다.
i번째 원소를 삭제한다.
원소 x를 삭제한다.
i번째 원소를 알려준다.
원소 x가 몇 번째 원소인지 알려준다.
리스트의 사이즈(원소의 총 수)를 알려준다.

• 파이썽능 리스트를 기본 자료구조로 제공하며, 위 작업보다 훨씩 더 많은 작업을 지원함
• 자바는 언어 자체에서 리스트를 java.util 패키지에서 제공함

 

 

배열 리스트 ArrayList

1. 구성요소

• 내부배열 : ArrayList는 내부적으로 배열(Object[])을 사용해 데이터를 저장. 이 배열은 필요에 따라 동적으로 크기가 조정됨.
• 용량 : 내부 배열의 현재 크기. ArrayList에 요소를 추가할 때 내부 배열의 크기가 부족하면 배열이 자동으로 재할당되어 크기가 증가함.
• 크기 : ArrayList에 실제 저장된 요소의 수. size() 메서드를 통해 알 수 있음

 

2. 작동 원리

• 동적 배열 : 처음에는 기본 크기의 배열을 할당. 요소가 추가될 때마다 배열의 크기가 부족하면 더 큰 새 배열을 만들고, 기존 요소들을 새 배열로 복사.
• 인덱스 접근 : ArrayList는 인덱스를 통한 빠른 접근이 가능. get(int index) 메서드를 사용하여 특정 인덱스의 요소를 빠르게 검색할 수 있음

 

3. 주요 메서드

• add(E element) : 리스트 끝에 요소 추가
• add(int index, E element) : 지정된 인덱스에 요소를 추가. 해당 인덱스와 그 이후의 요소들은 뒤로 이동
• remove(int index): 지정된 인덱스의 요소를 제거하고, 뒤에 있는 요소들을 앞으로 이동
• get(int index) : 지정된 인덱스에 있는 요소를 반환
• set(int index, E element) : 지정된 인덱스의 요소를 새 요소로 바꿈
• size() : 리스트에 저장된 요소의 수를 반환
• clear() : 리스트의 모든 요소를 제거
• contains(Object o) : 리스트가 특정 요소를 포함하고 있는지 확인. 포함하고 있으면 true를, 아니면 false를 반환
• indexOf(Object o) : 특정 요소가 리스트 내에서 처음으로 나타나는 위치의 인덱스를 반환. 리스트에 요소가 없으면 -1을 반환
• lastIndexOf(Object o) : 특정 요소가 리스트 내에서 마지막으로 나타나는 위치의 인덱스를 반환
• toArray() : 리스트의 요소들을 배열로 변환하여 반환
• subList(int fromIndex, int toIndex) : 리스트의 일부분을 뷰(view)로 반환
• iterator() : 리스트의 요소들을 순회할 수 있는 Iterator 객체를 반환
• forEach(Consumer<? super E> action) : 리스트의 모든 요소에 대해 주어진 작업을 수행
• sort(Comparator<? super E> c) : 리스트를 주어진 비교자(comparator)에 따라 정렬
• isEmpty() : 리스트가 비어있는지 여부를 확인. 비어있으면 true, 그렇지 않으면 false를 반환

 

 

연결 리스트 LinkedList

1. 구성요소

• 노드(Node) : LinkedList의 각 요소는 노드로 구현됨. 각 노드는 데이터와 다음 노드(및 이전 노드)에 대한 참조를 가짐
• 헤드(Head)와 테일(Tail) : 리스트의 시작 부분을 가리키는 헤드와 끝 부분을 가리키는 테일이 있음. 이것은 리스트의 처음과 끝에 접근을 용이하게 함

 

2. 작동 원리

• 연결 구조 : LinkedList는 노드들이 서로 연결되어 있는 구조를 가짐. 각 노드는 다음 노드에 대한 참조(그리고 이중 연결 리스트인 경우 이전 노드에 대한 참조)를 가지고 있음
• 동적 크기 조정 : 요소가 추가되거나 제거될 때, 노드들 사이의 연결이 조정됨. 리스트의 크기는 동적으로 변함
• 빠른 삽입과 삭제 : 특정 위치에 삽입하거나 삭제할 때, 연결만 변경하면 되므로 ArrayList에 비해 더 빠름

 

3, 주요 메서드

• add(E element) : 리스트의 끝에 요소를 추가
• add(int index, E element) : 지정된 인덱스에 요소를 추가
• remove(int index) : 지정된 인덱스의 요소를 제거
• get(int index) : 지정된 인덱스에 있는 요소를 반환
• set(int index, E element) : 지정된 인덱스의 요소를 새 요소로 바꿈
• size() : 리스트에 저장된 요소의 수를 반환
• clear() : 리스트의 모든 요소를 제거
• contains(Object o ): 리스트가 특정 요소를 포함하고 있는지 확인
• indexOf(Object o) : 특정 요소의 인덱스를 반환
• addFirst(E e) / offerFirst(E e): 리스트의 시작 부분에 요소를 추가
• addLast(E e) / offerLast(E e): 리스트의 끝 부분에 요소를 추가
• removeFirst() / pollFirst(): 리스트의 첫 번째 요소를 제거하고 반환. 리스트가 비어있을 경우 예외를 던지고, pollFirst()는 null을 반환
• removeLast() / pollLast(): 리스트의 마지막 요소를 제거하고 반환. removeLast()는 리스트가 비어있을 경우 예외를 던지고, pollLast()는 null을 반환
• getFirst() / peekFirst(): 리스트의 첫 번째 요소를 반환하지만 제거하지는 않음. getFirst()는 리스트가 비어있을 경우 예외를 던지고, peekFirst()는 null을 반환
• getLast() / peekLast(): 리스트의 마지막 요소를 반환하지만 제거하지는 않음. getLast()는 리스트가 비어있을 경우 예외를 던지고, peekLast()는 null을 반환
• iterator(): 리스트 요소를 순차적으로 접근할 수 있는 Iterator 객체를 반환
• descendingIterator(): 리스트 요소를 역순으로 접근할 수 있는 Iterator 객체를 반환

 

배열 리스트와 연결 리스트 비교

내부구조

ArrayList	내부적으로 크기가 가변적인 배열을 사용합니다. 배열 인덱스를 통해 요소에 접근하기 때문에 요소의 검색 및 접근이 빠릅니다.
LinkedList	각 요소가 노드 형태로 이루어져 있고, 각 노드가 다음 노드를 가리키는 포인터를 갖고 있습니다. 이중 연결 리스트인 경우, 각 노드는 이전 노드를 가리키는 포인터도 갖고 있습니다.

 

성능

ArrayList	검색: 인덱스를 통한 빠른 접근으로 검색이 매우 빠릅니다. 삽입/삭제: 리스트 중간에 요소를 삽입하거나 삭제하는 경우, 배열의 재조정이 필요하여 비효율적일 수 있습니다
LinkedList	검색: 특정 인덱스의 요소에 접근하기 위해서는 리스트를 순차적으로 탐색해야 하므로 느릴 수 있습니다. 삽입/삭제: 리스트의 어느 위치에서나 요소를 빠르게 삽입하거나 삭제할 수 있습니다. 특히 리스트의 시작 또는 끝에서는 매우 빠릅니다.

• 정렬된 상태의 배열 리스트에서 원소를 log n 시간에 검생할 수 있게 하는 알고리즘 : 이진 탐색 알고리즘

 

메모리 사용

ArrayList	크기가 변경될 때마다 새로운 배열을 생성하고 기존 요소를 복사해야 하므로 메모리 낭비가 발생할 수 있습니다. 하지만 각 요소에 대한 오버헤드는 적습니다.
LinkedList	각 요소가 추가 메모리(포인터)를 사용합니다. 따라서 메모리 사용량이 더 클 수 있습니다.

 

사용 사례

ArrayList	요소의 빈번한 접근이 필요하고, 크기 변경이 드문 경우에 적합합니다.
LinkedList	데이터의 빈번한 추가 또는 삭제가 필요한 경우, 특히 시작이나 끝 부분에서 작업이 이루어질 때 적합합니다.

 

• ArrayList
  • 연속된 공간에 원소를 저장함. 다음 원소에 대한 링크가 필요없으므로 원소 하나당 필요한 공간이 상대적으로 작음
  • 장점: 빠른 인덱스 기반 접근
  • 단점: 크기 변경 및 중간 삽입/삭제의 비효율성
• LinkedList
  • 공간의 연속성 없음. 다음 원소의 링크를 위한 공간이 추가로 필요함.
  • 장점: 양 끝에서의 빠른 삽입/삭제
  • 단점: 인덱스를 통한 접근의 비효율성, 추가적인 메모리 사용

 

 

리스트의 장점과 단점

장점

동적 크기 조정: 리스트는 동적으로 크기가 조정됩니다. 따라서 미리 크기를 지정할 필요가 없으며, 요소를 추가하거나 제거할 때 리스트의 크기가 자동으로 조절됩니다.

순서 유지: 리스트는 요소들을 추가한 순서대로 저장하며, 각 요소는 특정 인덱스에 위치합니다. 이로 인해 순서가 중요한 데이터를 다룰 때 유용합니다.

중복 허용: 리스트는 동일한 값을 가진 요소들을 여러 개 포함할 수 있습니다.

데이터 접근 및 조작의 유연성: 리스트는 데이터를 추가, 제거, 검색하는 등의 다양한 조작을 지원합니다. 특히 인덱스를 통한 빠른 접근이 가능한 ArrayList는 데이터 검색에 유리합니다.

 

단점

비효율적인 메모리 사용: ArrayList는 크기 조정 시 추가 메모리를 사용하며, LinkedList는 각 요소마다 추가 메모리를 사용합니다.

중간 삽입/삭제의 비효율성: ArrayList에서 중간에 요소를 삽입하거나 삭제하는 것은 비효율적입니다. 리스트 전체를 재조정해야 하기 때문입니다. 반면, LinkedList는 이 부분에서 더 효율적입니다.

랜덤 접근의 비효율성: LinkedList는 인덱스를 통한 랜덤 접근이 비효율적입니다. 특정 인덱스의 요소에 접근하기 위해서는 리스트를 처음부터 순회해야 하기 때문입니다.

캐시 활용의 비효율성: LinkedList는 메모리 상의 연속적인 공간에 데이터를 저장하지 않기 때문에, CPU 캐시를 효율적으로 활용하기 어렵습니다.

 

연결리스트의 확장

기본적인 연결 리스트의 불편함을 해소하기 위한 확장 버전

1. 이중 연결 리스트 (Doubly Linked List)

• 특징: 각 노드가 두 개의 포인터를 가지고 있으며, 하나는 이전 노드를 가리키고 다른 하나는 다음 노드를 가리킵니다.
• 장점: 양방향으로의 탐색이 가능하므로, 특정 상황에서 탐색 효율이 개선됩니다. 또한, 노드의 삽입과 삭제가 더욱 유연해집니다.
• 단점: 추가적인 메모리가 필요합니다(이전 노드를 가리키는 포인터).

2. 순환 연결 리스트 (Circular Linked List)

• 특징: 마지막 노드가 첫 번째 노드를 가리키는 형태로, 리스트의 끝과 시작이 연결되어 있습니다.
• 장점: 리스트의 끝에서 시작으로의 이동이 간단해지며, 순환 구조를 필요로 하는 특정 알고리즘에 적합합니다.
• 단점: 순환 구조로 인해 리스트의 끝을 식별하는 것이 복잡해질 수 있습니다.

3. 정렬된 연결 리스트 (Sorted Linked List)

• 특징: 노드들이 특정 기준에 따라 정렬된 순서로 유지되는 연결 리스트입니다.
• 장점: 항상 정렬된 상태를 유지하므로, 정렬된 데이터에 대한 빠른 검색이 가능합니다.
• 단점: 삽입 연산이 더 복잡해질 수 있습니다. 적절한 위치를 찾아 삽입해야 하기 때문입니다.

4. 자기 조정 리스트 (Self-adjusting Linked List)

• 특징: 데이터에 접근할 때마다 해당 노드를 리스트의 시작 부분으로 이동시키는 연결 리스트입니다.
• 장점: 자주 접근하는 요소에 대해 빠른 접근이 가능해집니다.
• 단점: 데이터 접근 시 매번 리스트 구조를 조정해야 하므로, 오버헤드가 발생할 수 있습니다.

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」