Java ArrayList 와 LinkedList

Java의 ArrayList와 LinkedList는 둘 다 List 인터페이스를 구현하는 클래스로서 데이터를 순차적으로 저장하고 관리할 수 있는 컬렉션입니다. 그러나 두 클래스는 내부적인 데이터 구조와 성능 면에서 중요한 차이점을 가지고 있습니다.

1. ArrayList: ArrayList는 내부적으로 배열을 사용하여 데이터를 저장합니다. 이렇게 배열을 사용하면 인덱스를 통해 데이터에 빠르게 액세스할 수 있으므로 검색 작업에서 뛰어난 성능을 보입니다. 그러나 ArrayList는 요소의 추가와 삭제에 있어서는 성능이 상대적으로 떨어집니다. 특히, 리스트의 중간에 있는 요소를 추가하거나 삭제하는 경우, 나머지 요소들을 이동시켜야 하므로 비효율적입니다.

2. LinkedList: LinkedList는 내부적으로 이중 연결 리스트를 사용하여 데이터를 저장합니다. 각 요소(노드)는 데이터와 두 개의 링크(이전 요소와 다음 요소를 가리키는 링크)를 가지고 있습니다. 이 구조 덕분에 데이터의 추가와 삭제가 상대적으로 빠르며, 리스트의 어느 위치에서든 상수 시간에 요소를 추가하거나 삭제할 수 있습니다. 그러나 이러한 이점은 검색 작업에 대한 성능 저하로 이어집니다. LinkedList에서 특정 인덱스의 요소를 찾기 위해서는 처음이나 끝부터 요소를 순차적으로 탐색해야 하므로 시간이 더 많이 걸립니다.

따라서, 어떤 List 구현체를 사용할지 결정할 때는 해당 컬렉션을 어떻게 사용하려는지에 따라 결정해야 합니다.
데이터 검색이 주된 작업이라면 ArrayList가 더 적합할 수 있으며, 데이터의 추가와 삭제가 빈번하게 일어나는 경우에는 LinkedList가 더 적합할 수 있습니다.

Array List 작동 방법

arrayList 에서 데이터를 추가하게 되면 ,
추가하거나 삭제할 경우 어떻게 작동하게 되는지 자세히 알려줘 !

ArrayList는 내부적으로 동적 배열을 사용하여 데이터를 저장하고 관리합니다. 이는 고정 크기의 배열과는 달리 크기를 동적으로 확장하거나 축소할 수 있다는 특징이 있습니다. 데이터가 추가되거나 삭제될 때마다 ArrayList는 다음과 같은 방식으로 작동합니다:

데이터 추가

• 리스트의 끝에 추가: 리스트의 끝에 데이터를 추가하는 경우에는, ArrayList가 현재 가득 찼는지 아닌지 확인합니다. 만약 ArrayList가 이미 가득 찬 상태라면, 내부적으로 더 큰 배열을 생성하고 기존의 모든 요소를 새 배열로 복사합니다. 이 과정은 시간이 약간 걸리며, 이를 "resizing"이라고 합니다. 그 후 새 요소가 새 배열의 끝에 추가됩니다. 이러한 방식으로, ArrayList는 필요에 따라 크기를 자동으로 확장할 수 있습니다.

• 리스트의 중간에 추가: 리스트의 중간에 데이터를 추가하는 경우에는, 해당 위치와 그 이후의 모든 요소를 한 칸씩 뒤로 이동시켜야 합니다. 이는 모든 이후의 요소에 대한 인덱스를 변경하므로 시간이 더 많이 걸립니다. 만약 배열이 이미 가득 차 있어서 더 큰 배열로 복사하는 과정이 필요한 경우에는, 추가적인 시간이 더 필요하게 됩니다.

데이터 삭제

• 리스트의 끝에서 삭제: 리스트의 끝에서 요소를 삭제하는 경우에는, 그냥 해당 요소를 null로 설정하고 리스트의 크기를 하나 줄입니다. 이 과정은 상수 시간에 완료됩니다.

• 리스트의 중간에서 삭제: 리스트의 중간에서 요소를 삭제하는 경우에는, 삭제된 요소 이후의 모든 요소를 한 칸씩 앞으로 이동시켜야 합니다. 이는 모든 이후의 요소에 대한 인덱스를 변경하므로 시간이 더 많이 걸립니다.

위와 같은 방식으로 ArrayList는 데이터의 추가와 삭제를 처리합니다. 이런 작동 방식 때문에, ArrayList는 데이터 검색에는 강점을 가지지만, 데이터의 추가나 삭제(특히 중간에서의 추가나 삭제)에서는 비효율적일 수 있습니다.

Linked List 작동방법

LinkedList는 List 인터페이스를 구현하는 컬렉션 클래스로, 데이터의 저장 및 관리를 위해 내부적으로 '이중 연결 리스트'라는 데이터 구조를 사용합니다.
이중 연결 리스트는 각 요소(노드)가 앞과 뒤의 두 요소를 가리키는 링크를 가지고 있는 데이터 구조입니다.

LinkedList의 작동 방식은 아래와 같습니다:

데이터 추가

• 리스트의 끝에 추가: 리스트의 끝에 요소를 추가하려면, 새로운 노드를 생성하고, 마지막 노드의 '다음' 링크를 새 노드로 설정하고, 새 노드의 '이전' 링크를 마지막 노드로 설정합니다. 이 과정은 상수 시간에 완료됩니다.

• 리스트의 중간에 추가: 리스트의 중간에 요소를 추가하려면, 먼저 새 요소가 추가될 위치를 찾아야 합니다. 이 작업은 O(n)의 시간이 걸릴 수 있습니다. 위치를 찾은 후에는 새 노드를 생성하고, 적절한 '이전'과 '다음' 링크를 설정하여 새 노드를 리스트에 연결합니다. 이 작업은 상수 시간에 완료됩니다.

데이터 삭제

• 리스트의 끝에서 삭제: 리스트의 끝에서 요소를 삭제하려면, 마지막 노드를 찾고, 마지막 노드의 '이전' 노드의 '다음' 링크를 null로 설정하여 마지막 노드를 리스트에서 분리시킵니다. 이 작업은 상수 시간에 완료됩니다.

• 리스트의 중간에서 삭제: 리스트의 중간에서 요소를 삭제하려면, 먼저 삭제될 요소의 위치를 찾아야 합니다. 이 작업은 O(n)의 시간이 걸릴 수 있습니다. 위치를 찾은 후에는 해당 노드의 '이전' 노드의 '다음' 링크를 해당 노드의 '다음' 노드로 설정하고, 해당 노드의 '다음' 노드의 '이전' 링크를 해당 노드의 '이전' 노드로 설정하여 해당 노드를 리스트에서 분리시킵니다. 이 작업은 상수 시간에 완료됩니다.

이와 같이 LinkedList는 노드의 추가 및 삭제를 효율적으로 처리할 수 있지만, 특정 인덱스 위치의 요소에 액세스하려면 해당 위치까지 순차적으로 탐색해야 하므로 시간이 더 많이 걸릴 수 있습니다.