[Java] LinkedList

리스트

1. ArrayList
2. LinkedList
3. Vector
4. Stack

✍️ LinkedList

✏️ LinkedList 란?

• 배열은 모든 데이터가 연속적으로 존재하지만 LinkedList 는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있습니다.
• LinkedList 의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있습니다.
• 데이터 삭제 시에는, 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 됩니다.
• 데이터 삽입 시에는, 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하면 됩니다.

  

  
  

✏️ 선언

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        System.out.println(list);  // [Apple, Banana, Cherry]
    }
}

✏️ 이중 연결리스트 (Doubly Linked List)

• LinkedList 는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵습니다.
• 이 점을 보안하기 위해 더블 링크드 리스트 (이중 연결리스트;Doubly Linked List)를 사용합니다.
• 실제로 LinkedList 클래스는 이름과 달리 Doubly Linked List 로 구현되어 있습니다.

✏️ 이중 원형 연결리스트 (Doubly Circular Linked List)

• Doubly Linked List 의 접근성을 보다 향상시킨 것이 Doubly Circular Linked List 입니다.
• 이는 마지막 요소의 다음 요소가 첫번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 됩니다.

✏️ ArrayList와 LinkedList 차이

🎨  ArrayList

• 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산식 (인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기) 으로 원하는 요소의 주소를 얻어서 데이터를 곧바로 읽어올 수 있습니다.

🎨  LinkedList

• 중간 요소를 추가/삭제하는 경우, LinkedList 는 각 요소간의 연결만 변경해주면 되기 때문에 처리 속도라 상당히 빠릅니다.
• 데이터가 많을 수록 접근성이 떨어집니다.

✏️ 주요 메서드 및 시간 복잡도

🎨  1. boolean add(Object O)

• 시간 복잡도: O(1)
• 지정된 객체를 Linked List의 끝에 추가

🎨  2. void add(int index, Object O)

• 시간 복잡도: O(n)
• 지정된 인덱스에 객체를 추가합니다.

🎨  3. void clear()

• 시간 복잡도: O(n)
• LinkedList의 모든 요소를 삭제합니다.

🎨  4. boolean contains(Object O)

• 시간 복잡도: O(n)
• 지정된 객체가 LinkedList에 포함되어 있는지 알려줍니다

🎨  5. boolean containsAll(Collection c)

• 시간 복잡도: O(n*m)
• 지정된 컬렉션의 모든 요소가 포함되었는지 알려줍니다.

🎨  6. Object get(int index)

• 시간 복잡도: O(n)
• 지정된 인덱스의 객체를 반환합니다.

🎨  7. int indexOf (Object o)

• 시간 복잡도: O(n)
• 지정된 객체가 저장된 위치를 반환합니다.

🎨  8. boolean isEmpty()

• 시간 복잡도: O(1)
• LinkedList가 비어있는지 알려줍니다.

🎨  9. int lastIndexOf(Object o)

• 시간 복잡도: O(n)
• 지정된 객체의 위치를 반환합니다.

🎨  10. Object remove(int index)

• 시간 복잡도: O(n)
• 지정된 위치의 객체를 제거합니다.

🎨  11. boolean removeAll(Collection c)

• 시간 복잡도: O(n*m)
• 지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제합니다.

🎨  12. boolean retainAll(Collection c)

• 시간 복잡도: O(n*m)
• 지정된 컬렉션의 요소의 모든 요소가 포합되어 있는지 확인합니다.

🎨  13. Object set(int index, Object element)

• 시간 복잡도: O(n)
• 지정된 위치의 객체를 주어진 객체로 변경합니다.

🎨  14. int size()

• 시간 복잡도: O(1)
• 저장된 객체의 수를 반환합니다.

🎨  15 Object[] toArray()

• 시간 복잡도: O(n)
• LinkedList에 저장된 객체를 배열로 반환합니다.

🎨  16. Object[] toArray(Object[] a)

• 시간 복잡도: O(n)
• LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환합니다.

🎨  17. Object element()

• 시간 복잡도: O(1)
• LinkedList의 첫 번째 요소를 반환합니다.