[자료구조] 2-2 리스트(List) - Linked List, Doubly Linked List

728x90

 

자료구조도

 

 

Linked List 특징(feat. 장단점)

이미지 출처: https://code-lab1.tistory.com/2

 

Linked List는 연결 리스트라고도 한다.

 

1-1. 장점

- 미리 데이터 공간을 할당하지 않아도 된다. 따라서 데이터가 필요할 때 저장공간을 만들기 때문에 낭비적인 요소가 별로 없다고 볼수도 있다.

cf) 배열은 미리 할당해야함.

 

1-2. 단점

- 하지만 연결을 위한 별도 데이터 공간, 즉 다음 데이터 주소를 넣는 공간(포인터)이 필요하다는 측면에서 바라보면, 저장공간의 효율성이 좋다고 볼 수는 없다.

※ cf) 데이터와 포인터를 합쳐서 노드라고 한다.

 

이미지 출처: https://wakestand.tistory.com/106

 

- 또한 위 이미지에서 볼 수 있듯, 배열과 다르게 이어져있는 자료구조가 아니기때문에 특정 값을 찾기 위해선 맨 앞(head)에서부터 탐색하여 포인터들을 타고 찾게 되기때문에 접근(탐색) 속도가 느리다.

- 중간에 위치한 노드를 삭제 / 중간에 노드를 추가할 경우, 앞 뒤 데이터 연결을 재구성(포인터 주소값들의 변경)하는 부가적인 작업이 필요하다.

 

LinkedList 선언과 메소드

- add(obj)
- add(idx, obj)
- set(idx, obj)
- remove(idx)
- clear()

cf)
- removeAll(linkedList)

 

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        
        // LinkedList 선언
        List<String> linkedList = new LinkedList<>();

        // 값 추가
        linkedList.add("banana");
        linkedList.add("banana");
        
        // add(idx, obj): 해당 idx에 obj 추가
        linkedList.add(1, "apple");

        System.out.println(linkedList); // [banana, apple, banana]
        
        // 값 변경
        linkedList.set(2, "apple");
        System.out.println(linkedList); // [banana, apple, apple]
        
        // 값 삭제
        linkedList.remove(0);
        System.out.println(linkedList); // [apple, apple]

        linkedList.clear();
        System.out.println(linkedList); // []
    }
}

 

다양한 Linked List 구조 중 더블 링크드 리스트(Doubly Linked LIst)

더블 링크드 리스트(Doubly Linked List)는 이중 연결 리스트라고도 한다.

더블 링크드 리스트는 Linked List의 단점을 보안하기 위해 등장했다.

예를 들어 Linked List는 HEAD부터 시작해서 찾아가기 때문에 99번째 노드와 같이 뒤쪽에 위치한 노드를 찾아가는 데 오래 걸린다.

 

이미지 출처: https://www.tech-faq.com/doubly-linked-list.html

 

이를 보안하기 위한 방법으로 더블 링크드 리스트는 위 이미지처럼 head와 tail 그리고 한 노드에 이전과 다음 노드를 가리키는 포인터 2개를 갖는 구조를 띄고 있다.

하지만 그렇기 때문에 저장공간을 많이 차지한다. 또한 아쉽게도 Java에서 Doubly Linked List 라이브러리를 지원해주지 않는다.