[Java - 자료구조] LinkedList와 ArrayList란? | 민민의 하드디스크 - 티스토리

LinkedList   vs   ArrayList

 

1. LinkedList(링크드 리스트)란?

[데이터1] -> [데이터2] -> [데이터3] -> ... -> [데이터N] -> null

링크드 리스트는 노드들이 데이터와 다음 노드를 가리키는 링크(포인터)로 이루어진 자료 구조이다.
각 노드는 메모리 어디든 저장될 수 있으며, 데이터 추가 및 삭제가 유연하게 이루어지며, 데이터에 대한 접근은 순차적으로 이루어져야 하기 때문에 접근 속도가 O(n)이다.

LinkedList(링크드 리스트) 예시 코드

// LinkedList 선언
LinkedList<String> linkedList = new LinkedList<>();

// 데이터 추가
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");

String 타입으로 선언했으며, "A" - "B" - "C" 의 데이터 순서를 가진다.
링크드리스트는 값을 추출할 때, 시간복잡도가 O(n) 이기 때문에 iterator()를 사용하여 값을 추출하는 것이 일반적이다.
링크드리스트: 값 추출 시간복잡도 O(n)

Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

 

 

2. ArrayList(어레이 리스트)란?

[데이터1] [데이터2] [데이터3] ... [데이터N]

어레이 리스트는 연속된 메모리 위치에 데이터를 저장하는 자료 구조이다.
인덱스를 사용하여 데이터에 빠르게 접근할 수 있으며, 크기를 동적으로 조절할 수 있다.
데이터 추가 및 삭제가 어레이 복사를 수반하므로, 이 작업은 느릴 수 있다.

ArrayList(어레이 리스트) 예시 코드

// ArrayList 선언
ArrayList<String> arrayList = new ArrayList<>();

// 데이터 추가
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");

어레이리스트는 링크드리스트와 다르게 배열이기 때문에 특정 인덱스에 채워지게 되므로, 아래와 같이 인덱스 위치의 값을 뽑아온다.
어레이리스트: 값 추출 시간복잡도 O(1)

for (int i = 0; i < arrayList.size(); i++) {
            System.out.println(arrayList.get(i));
        }

 

 

3. 두 자료구조의 장단점

LinkedList의 장단점

• 장점
  
  • 데이터 추가/삭제가 빈번한 경우에 유용하다.
  • 중간에 데이터를 삽입하거나 삭제할 때 효율적이다.
• 단점
  
  • 특정 위치의 데이터에 접근하는데 O(n)의 시간이 소요된다.
  • 각 노드에 링크를 저장해야 하므로 메모리 공간이 더 많이 소요될 수 있다.

ArrayList의 장단점

• 장점
  • 특정 인덱스에 직접 접근할 수 있어 검색 속도가 빠르다(O(1)).
  • 데이터를 읽는 연산이 많은 경우 유용하다.
• 단점
  
  • 데이터 추가/삭제가 빈번한 경우에는 어레이 복사 등의 작업으로 인해 성능이 저하될 수 있다.
  • 크기를 동적으로 조절하는데 비용이 크다.

 

 

4. LinkedList   vs   ArrayList

어떤 상황에 어떤 자료구조를 사용하면 좋을까?

LinkedList는 데이터의 추가/삭제가 빈번한 상황에서 성능이 좋지만, 특정 위치의 데이터 접근이 느리다.
ArrayList는 데이터 접근이 빈번한 상황에서 성능이 우수하며, 크기를 동적으로 조절하는데도 효과적이지만, 데이터 추가/삭제가 빈번한 경우에는 성능 저하가 발생할 수 있다.

결론

만약 리스트의 크기가 자주 변경되고 중간에 데이터를 추가 또는 삭제해야 하는 경우에는 링크드 리스트가 적합할 수 있다. 그러나 데이터를 자주 찾아야 하거나 인덱스를 사용해 직접 접근해야 하는 경우에는 어레이 리스트가 성능적으로 유리할 수 있다. 자료구조에 따라 장단점이 명확하기에, 상황에 맞게 잘 선택해서 사용하면 될 것 같다...