연결 리스트(Linked List)란?

🚀 연결 리스트(Linked List)란 무엇인가요?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

*포인터는 다음이나 이전의 노드와의 연결을 담당합니다. 🚄

🌟 연결 리스트의 장단점

👍 장점

- 동적 크기

: 연결 리스트는 동적으로 데이터를 저장하기 때문에, 필요할 때마다 메모리를 할당 받을 수 있습니다.

- 데이터 삽입 및 삭제 용이

: 포인터를 변경하는 것만으로 데이터의 삽입 및 삭제가 가능하여 상대적으로 빠릅니다.

👎 단점

- 선형 접근

: 인덱스를 통한 접근이 없기 때문에, 원하는 데이터를 찾기 위해서는 처음부터 노드를 따라가야 합니다.

- 메모리 오버헤드

: 각 노드에 데이터 외에 포인터 정보를 저장해야 하기 때문에 메모리 사용이 상대적으로 많습니다.

🕒 연결 리스트의 시간 복잡도

접근 시간: O(n) - 순차적인 접근이 필요
검색 시간: O(n) - 순차적인 검색이 필요
삽입/삭제 시간: O(1) - 포인터를 변경해주기만 하면 됨. 단, 이전/다음 노드의 포인터를 얻기 위한 검색 시간은 제외.

🤔 연결 리스트는 언제 사용하면 좋을까요?

- 크기를 알 수 없는 데이터를 다룰 때

: 미리 크기를 알 수 없고, 동적으로 크기가 변경되어야 하는 상황에서 유용합니다.

- 데이터의 삽입과 삭제가 빈번하게 일어나는 경우

: 포인터 조작만으로 삽입과 삭제를 할 수 있기 때문에 해당 연산이 빈번한 경우 유용합니다.

- 메모리를 효율적으로 사용해야 하는 경우

: 정확한 크기만큼의 메모리를 동적으로 할당받을 수 있으므로 메모리를 효율적으로 사용할 수 있습니다.