[Study] LinkedList

LinkedList란?

- 선형 자료구조

- 데이터와 포인터를 가진 노드가 연결되어 있는 리스트

- 각 노드가 다음 노드를 가리키는 형태

- 노드는 동적으로 할당되므로 노드들 사이의 주소 값은 연속적이지 않다.

- 중간 인덱스에 바로 접근이 불가능하다. 즉 Head 부터 다음 노드로 이동하며 탐색해야 한다.

 

- Head -> Node들 -> Tail 로 구성. 

- Singly linked list, Doubly linked list, 원형 linked list 존재

 

LinkedList의 장단점

 

장점

- 데이터의 삽입과 삭제가 편하다

- 동적 메모리 할당 

    : 실행 중 데이터 크기를 유연하게 조정할 수 있다.

- 메모리 효율

    : 불필요한 메모리를 미리 할당하지 않아 메모리 사용 효율성이 높다

- 다양한 타입의 데이터를 한 리스트에 저장 가능

 

단점

- 특정 요소를 찾는데 시간복잡도가 오래걸린다

    : 삽입과 삭제 자체의 시간복잡도는 O(1)이나 삽입, 삭제하고자 하는 값을 탐색하는 수행시간이 O(N)

    : 배열은 인덱스만 있으면 삽입 삭제가 O(1)이 걸린다

- 데이터 + 포인터를 함께 저장해야 하므로 추가적인 메모리를 필요로 한다

 

사용하면 좋은 경우
- 실행 중 데이터 크기를 유연하게 조정해야 할 때
- 다양한 타입의 데이터를 한 리스트에 저장하고 싶을 때

사용하면 불리한 경우
- 리스트 내 특정 요소를 찾아볼 경우가 많을 때