Collection -List, ArrayList, LinkedList

✅ List Interface

List 인터페이스는 자바 프로그래밍 언어에서 제공하는 인터페이스 중 하나입니다. 이 인터페이스는 순서가 있는 요소의 컬렉션을 나타내며, 중복된 요소를 포함할 수 있습니다. List 인터페이스는 자바의 컬렉션 프레임워크에 속하며, 배열과 유사한 동작을 수행하는 동적인 크기의 리스트를 제공합니다.

List 인터페이스는 java.util 패키지에 정의되어 있으며, java.util.Collection 인터페이스를 확장하고 있습니다. 따라서 List는 Collection 인터페이스에서 정의된 모든 메서드를 상속받습니다. 또한 List 인터페이스는 자체적으로 인덱스를 사용하여 요소에 접근하는 메서드를 추가로 정의하고 있습니다.

. ➡️ List 인터페이스의 주요 특징은 다음과 같습니다:

• 순서 있음

  List의 요소는 순서를 가지고 있으며, 요소의 삽입 순서를 유지합니다. 따라서 요소를 추가한 순서대로 접근할 수 있습니다.

• 중복 요소 포함

  List는 중복된 요소를 포함할 수 있습니다. 즉, 동일한 값을 가진 요소를 여러 개 가질 수 있습니다.

• 인덱스 기반 접근

  List는 인덱스를 사용하여 요소에 접근할 수 있습니다. 인덱스는 0부터 시작하며, 요소의 위치를 지정하는 정수값으로 사용됩니다. 따라서 List에서는 인덱스를 통해 요소를 검색하거나 수정할 수 있습니다.

✅ ArrayList

ArrayList는 자바에서 제공하는 동적 배열 클래스입니다. 기본적으로 java.util 패키지에 포함되어 있으며, 배열과 유사한 연속된 데이터 구조를 제공합니다. ArrayList는 객체를 저장하고 관리하기 위한 다양한 기능과 특징을 갖고 있습니다.

• 동적 크기

  ArrayList는 내부적으로 배열을 사용하며, 배열의 크기를 자동으로 조정할 수 있습니다. 초기에는 작은 크기로 시작하고, 원소를 추가하면서 필요에 따라 크기를 동적으로 조정합니다. 이를 통해 용량 관리에 대한 걱정을 할 필요 없이 편리하게 원소를 추가하고 삭제할 수 있습니다.

• 객체 저장

  ArrayList는 객체를 저장할 수 있는 클래스이므로, 다양한 종류의 객체를 저장할 수 있습니다. 객체의 타입에 제한이 없으며, 사용자가 정의한 클래스의 객체도 저장할 수 있습니다.

• 인덱스 기반 접근

  ArrayList는 내부적으로 인덱스를 사용하여 요소에 빠르게 접근할 수 있습니다. 인덱스를 이용하여 특정 위치의 원소를 삽입, 삭제, 수정하거나 조회할 수 있습니다. 이러한 특징으로 인해 빠른 검색 및 임의 접근이 필요한 경우에 유용합니다.

• 컬렉션 기능

  ArrayList는 컬렉션 프레임워크의 일부로, 컬렉션 인터페이스를 구현하고 있습니다. 따라서 다른 컬렉션 클래스와 함께 사용할 수 있는 일관된 인터페이스를 제공합니다. 예를 들어, ArrayList는 요소의 개수를 반환하는 size() 메서드, 모든 요소를 포함하는 배열을 반환하는 toArray() 메서드 등을 제공합니다.

➡️ ArrayList는 다음과 같은 상황에서 주로 사용됩니다.

1. 요소의 추가 및 삭제가 빈번한 상황

   ArrayList는 동적으로 크기를 조정할 수 있으므로, 요소의 추가와 삭제가 빈번한 경우에 유용합니다. 배열보다 유연하게 크기를 관리할 수 있기 때문에 효율적인 데이터 관리가 가능합니다.

2. 임의 접근이 필요한 경우

   ArrayList는 인덱스를 사용하여 임의의 위치에 있는 요소에 빠르게 접근할 수 있습니다. 따라서 데이터의 검색이나 수정이 빈번한 경우에 ArrayList를 활용할 수 있습니다.

3. 컬렉션 인터페이스와 함께 사용할 때

   ArrayList는 컬렉션 인터페이스를 구현하고 있으므로, 다른 컬렉션 클래스와 함께 사용하여 유연하고 일관된 코드를 작성할 수 있습니다. 예를 들어, 다른 컬렉션을 ArrayList로 변환하거나 ArrayList를 다른 컬렉션으로 변환하는 등의 작업이 필요한 경우에 사용될 수 있습니다.

👉 실시간으로 요소를 추가하거나 삭제해야 하는 데이터 관리 시스템이나 로그 기록 시스템 등과 인덱스를 사용하여 요소에 빠르게 접근할 필요가 있는 검색, 조회 등에 효율적입니다.

💡

—배열보다 ArrayList를 더 자주 사용하는 이유

• 동적 크기 조정

  ArrayList는 내부적으로 배열을 사용하지만, 배열과는 달리 크기를 자동으로 조정할 수 있습니다. 이로써 요소의 추가 및 삭제가 용이하며, 크기 관리에 대한 번거로움이 없습니다.

• 다양한 기능 제공

  ArrayList는 다양한 메서드를 제공하여 요소의 추가, 삭제, 검색, 정렬 등 다양한 기능을 쉽게 수행할 수 있습니다. 예를 들어, add(), remove(), get(), indexOf(), sort() 등의 메서드를 활용할 수 있습니다.

• 인덱스 관리의 간소화

  ArrayList는 내부적으로 인덱스를 자동으로 관리하여 개발자가 인덱스 계산이나 관리에 신경 쓸 필요가 없습니다. 인덱스를 사용하여 요소에 빠르게 접근할 수 있어 효율적인 데이터 처리가 가능합니다.

• 제네릭 타입 지원

  ArrayList는 제네릭 타입을 지원하여 타입 안정성을 제공합니다. 이를 통해 컴파일 시에 타입 검사를 할 수 있고, 타입 캐스팅과 관련된 오류를 방지할 수 있습니다. 배열은 공변성 때문에 타입 안정성이 떨어집니다.

• 컬렉션 프레임워크와 호환성

  ArrayList는 컬렉션 프레임워크의 일부로 List 인터페이스를 구현하고 있습니다. 이는 다른 컬렉션 클래스와의 호환성을 높여서 유연한 데이터 구조를 구성할 수 있도록 도와줍니다. 예를 들어, ArrayList를 다른 컬렉션 클래스로 변환하거나, 다른 컬렉션 클래스를 ArrayList로 변환하는 등의 작업이 쉽게 이루어집니다.

🔹 ArrayList의 주요 메소드

• ArrayList에 요소 추가하기 -add()

  import java.util.ArrayList;
  
  public class ArrayListExample {
      public static void main(String[] args) {
          ArrayList<String> fruits = new ArrayList<>();
  
          // 요소 추가
          fruits.add("Apple");
          fruits.add("Banana");
          fruits.add("Orange");
  
          // 결과 출력
          System.out.println(fruits); // [Apple, Banana, Orange]
      }
  }

• ArrayList에서 요소 제거하기 -remove()

  import java.util.ArrayList;
  
  public class ArrayListExample {
      public static void main(String[] args) {
          ArrayList<String> fruits = new ArrayList<>();
  
          // 요소 추가
          fruits.add("Apple");
          fruits.add("Banana");
          fruits.add("Orange");
  
          // 요소 제거
          fruits.remove("Banana");
  
          // 결과 출력
          System.out.println(fruits); // [Apple, Orange]
      }
  }

• ArrayList의 요소 순회하기 -for문, iterator

  import java.util.ArrayList;
  
  public class ArrayListExample {
      public static void main(String[] args) {
          ArrayList<String> fruits = new ArrayList<>();
  
          // 요소 추가
          fruits.add("Apple");
          fruits.add("Banana");
          fruits.add("Orange");
  
          // 요소 순회
          for (String fruit : fruits) {
              System.out.println(fruit);
          }
      }
  }

• ArrayList에서 특정 요소의 인덱스 찾기 -indexOf()

  import java.util.ArrayList;
  
  public class ArrayListExample {
      public static void main(String[] args) {
          ArrayList<String> fruits = new ArrayList<>();
  
          // 요소 추가
          fruits.add("Apple");
          fruits.add("Banana");
          fruits.add("Orange");
  
          // 특정 요소의 인덱스 찾기
          int index = fruits.indexOf("Banana");
  
          // 결과 출력
          System.out.println("Banana의 인덱스: " + index); // Banana의 인덱스: 1
      }
  }

✅ LinkedList

링크드 리스트는 컴퓨터 과학과 프로그래밍에서 데이터를 저장하고 조직화하는 데 사용되는 데이터 구조입니다. 링크드 리스트는 각각의 노드로 구성되며, 각 노드에는 데이터 요소와 다음 노드를 가리키는 참조(또는 링크)가 포함됩니다.

링크드 리스트의 기본 구성 요소는 노드입니다. 각 노드에는 일반적으로 데이터 부분과 다음 노드를 가리키는 포인터(또는 참조) 부분이 있습니다. 데이터 부분은 실제 값이나 정보를 저장하고, 다음 포인터는 시퀀스에서 다음 노드를 가리킵니다. 노드의 오른쪽에는 다음 요소의 주소가 포함되어 있고, 노드의 왼쪽에는 리스트 내의 이전 요소의 주소가 포함되어 있습니다.

LinkedList는 자바 컬렉션 프레임워크의 하나로, 더블 링크드 리스트(doubly linked list)로 구현된 데이터 구조입니다. 각 요소는 이전 요소와 다음 요소를 가리키는 링크(참조)를 가지고 있습니다. LinkedList는 동적인 크기 조정이 가능하며, 요소의 삽입, 삭제, 검색에 효율적입니다.

➡️LinkedList의 주요 특징은 다음과 같습니다.

1. 더블 링크드 리스트 구조

   LinkedList의 각 노드는 데이터 요소와 이전 노드와 다음 노드를 가리키는 두 개의 링크로 구성됩니다. 이 링크를 통해 순차적인 탐색, 요소의 삽입 및 삭제 작업을 수행할 수 있습니다.

2. 동적 크기 조정

   LinkedList는 내부적으로 연결된 노드들로 구성되어 있으며, 요소의 추가나 삭제 시 필요에 따라 크기를 동적으로 조정할 수 있습니다. 이는 배열(Array)과 달리 크기 제한에 대한 걱정 없이 요소를 추가하거나 삭제할 수 있다는 장점을 가지고 있습니다.

3. 느린 접근 시간

   LinkedList는 인덱스를 기반으로 한 빠른 랜덤 액세스를 제공하지 않습니다. 원하는 위치의 요소에 접근하기 위해서는 첫 번째 노드부터 순차적으로 탐색해야 합니다. 따라서 요소를 검색할 때는 LinkedList보다 배열(ArrayList 등)을 사용하는 것이 더 효율적입니다.

4. 중간 삽입 및 삭제의 효율성

   LinkedList는 중간에 요소를 삽입하거나 삭제하는 작업에 용이합니다. 이 작업은 해당 위치의 이전 노드와 다음 노드의 링크만 변경하면 되기 때문에 배열에 비해 효율적입니다.

👉 LinkedList는 요소가 리스트의 중간에 삽입되거나 제거되는 상황에서 특히 유용합니다. 또한 중복 요소와 다른 타입의 요소를 저장할 수 있습니다. 링크드 리스트에서 요소는 연속적인 메모리 위치에 저장되지 않기 때문입니다. 요소(일반적으로 노드라고 함)는 노드 부분의 왼쪽과 오른쪽을 이용하여 서로 연결하여 메모리의 여유 공간 어디에든 위치할 수 있습니다.

🔹Linked List는 어떻게 동작하는가?

➡️ LinkedList의 주요 기능과 특징을 정리해보겠습니다.

• 중복, null, 다른 타입의 요소를 저장할 수 있습니다.

• 여러 스레드가 동시에 동일한 LinkedList 객체에 접근할 수 있는 스레드 동기화가 지원되지 않습니다. 동기화되지 않았으므로 작업이 더 빠릅니다.

• 요소의 삽입과 제거가 빠릅니다. 각 요소의 추가 및 제거를 위한 요소들을 이동시킬 필요가 없기 때문입니다. Next와 Prev 요소에 대한 참조만 변경됩니다.

• 요소를 검색하는 것은 매우 느립니다. 요소에 도달하기 위해 시작점이나 끝점부터 순회해야 하기 때문입니다.

• "스택"으로 사용할 수 있습니다. pop() 및 push() 메서드를 사용하여 스택으로 동작할 수 있습니다.

• LinkedList는 무작위 액세스 인터페이스(Random Access Interface)를 구현하지 않습니다. 따라서 요소에 임의로 액세스(검색)할 수 없습니다. 주어진 요소에 액세스하려면 LinkedList에서 시작점이나 끝점부터 순회해야 합니다.

• ListIterator를 사용하여 LinkedList 요소를 Iterable 할 수 있습니다.

➡️ 위의 특징을 토대로 LinkedList가 어떻게 삽입과 삭제가 이루어지는지 살펴보겠습니다.

• Init

  초기 LinkedList에는 다음과 같은 데이터가 있다고 가정해 봅시다. 아래 그림과 같습니다.

  LinkedList<String> linkedlist = new LinkedList<>();
  linkedlist.add(0,"A");
  linkedlist.add(1,"B");
  linkedList.add(2,"C");
  linkedList.add(3,"D");

  

  위 LinkedList는 제네릭을 사용하여 String 타입의 객체를 저장하고 있습니다. 현재는 총 4개의 노드에 A, B, C, D 데이터를 가진 객체를 0~3까지 인덱스에 저장하였습니다. add() 메서드에서 인덱스를 지정하지 않을 경우, 현재 인덱스의 가장 마지막에 저장됩니다.

• add

  linkedlist.add(2,"G");

  

  링크드 리스트에 삽입 작업을 수행했습니다. add() 메서드를 사용하여 인덱스 위치 2에 요소 G를 추가했습니다. 링크드 리스트에서 삽입 작업이 발생할 때, 내부적으로 LinkedList는 메모리의 가용한 어떤 공간이든 G 요소를 가진 노드를 생성하고, 리스트 내의 어떤 요소도 이동하지 않고 Next와 Prev 포인터만 변경합니다. 위의 그림에서 업데이트된 LinkedList를 확인할 수 있습니다.

• delete

  linkedlist.remove(1);

  

  링크드 리스트에 삭제 작업을 수행했습니다. remove() 메서드를 사용하여 인덱스 위치 1에 요소 B를 삭제하였습니다. 삭제 작업이 발생하면 요소 B가 있는 노드가 삭제되고 다음과 이전 포인터가 변경됩니다. 삭제된 노드는 사용되지 않는 메모리가 됩니다. 따라서 Java는 가비지 컬렉션을 사용하여 사용되지 않는 메모리 공간을 정리합니다.

✅ LinkedList는 언제 사용할까?

➡️ LinkedList를 사용하기에 적합한 경우

Java 애플리케이션에서 LinkedList를 사용하는 가장 좋은 경우는 리스트의 중간에 요소를 추가하거나 제거하는 작업이 빈번한 경우입니다. 링크드 리스트에서의 요소 추가와 제거는 ArrayList와 비교했을 때 더 빠르기 때문에 이러한 경우에는 Java LinkedList가 가장 적합한 선택입니다.

• 아래 시나리오를 통해 예시를 들어보겠습니다.

  예를 들어 ArrayList에 100개의 요소가 있다고 가정해 봅시다. ArrayList에서 50번째 요소를 제거한다면, 51번째 요소는 50번째 위치로 이동하고, 52번째 요소는 51번째 위치로 이동하며, 다른 요소들에 대해서도 이러한 작업이 이루어져야 합니다. 이렇게 되면 요소의 이동에 많은 시간이 소요되어 ArrayList에서의 조작이 느려집니다.

  그러나 링크드 리스트의 경우, 링크드 리스트에서 50번째 요소를 제거한다면, 제거 후에 요소의 이동은 발생하지 않습니다. 오직 다음 노드와 이전 노드의 참조만 변경됩니다. 또한 LinkedList는 스택(LIFO) 또는 큐(FIFO) 데이터 구조가 필요한 경우에도 중복을 허용하여 사용할 수 있습니다.

➡️ LinkedList를 사용하기에 적합하지 않은 경우

LinkedList를 사용하는 최악의 경우는 링크드 리스트에서 요소를 검색(조회)하는 작업이 빈번한 경우입니다. ArrayList와 비교하여 링크드 리스트에서 요소를 검색하는 것은 매우 느리기 때문에 LinkedList는 최악의 선택입니다. LinkedList는 무작위 액세스 인터페이스를 구현하지 않습니다. 따라서 요소에 임의로 액세스(조회)할 수 없습니다. 시작점이나 끝점부터 순회하여 링크드 리스트의 요소에 도달해야 합니다.

• 아래 시나리오를 통해 예시를 들어보겠습니다.

  리스트에 10개의 요소가 있다고 가정해 봅시다. 링크드 리스트가 첫 번째 요소에 액세스하여 요소를 가져오는 데 1초가 걸린다고 가정해 봅시다. 첫 번째 노드에서 두 번째 요소의 주소가 사용 가능하므로, 두 번째 요소에 액세스하고 가져오기 위해서는 2초가 걸릴 것입니다. 마찬가지로, 리스트에서 9번째 요소를 가져오려면 LinkedList는 9초가 걸릴 것입니다. 왜냐하면 9번째 요소의 주소는 8번째 노드에 있고, 8번째 노드의 주소는 7번째 노드에 있기 때문입니다.

  그러나 리스트에 100만 개의 요소가 있고, 리스트에서 50만 번째 요소를 가져오려고 한다면 링크드 리스트는 50만 번째 요소를 액세스하고 가져오는 데 1년이 걸릴 수도 있습니다. 따라서 링크드 리스트는 링크드 리스트에서 요소를 검색하거나 탐색하는 경우에는 최악의 선택입니다.

  이 경우에는 ArrayList가 리스트에서 요소를 가져오는 데 가장 적합한 선택입니다. 왜냐하면 ArrayList는 무작위 액세스 인터페이스를 구현하기 때문에 임의의 위치에서 배열 리스트에서 요소를 매우 빠르게 가져올 수 있기 때문입니다.

---

🏷️이미지 출처와 참고한 사이트

ArrayList in Java | Initialize, Methods, Example - Scientech Easy

Learn ArrayList in Java with example program, syntax to declare and initialize ArrayList, ArrayList methods, generic ArrayList objects, add,

https://www.scientecheasy.com/2020/09/arraylist-in-java.html/

Insertion in Doubly Linked List in C | PrepInsta

On this page we will discuss Insertion in Doubly Linked List in C . Each node contains 2 pointers which helps to find previous and next node.

https://prepinsta.com/c-program/insertion-in-doubly-linked-list/

Collections in Java - Scaler Topics

Collections in Java is a framework that stores and manipulates a group of objects. Learn more on Scaler Topics.

https://www.scaler.com/topics/java/collections-in-java/

Uploaded by N2T