연결리스트란(Linked List)
연결리스트는 배열과 다른 종류의 데이터를 저장하는 자료구조
연결 리스트는 선형 자료구조로서, 각 노드가 다음 노드를 가리키는 형태를 가지고 있습니다. 이것은 마치 서로 꼬리를 물고 있는 것처럼 보일 수 있습니다. 각 노드는 동적으로 할당되므로, 노드들 사이의 주소 값은 연속적이지 않습니다.
반면에 배열은 연속된 메모리 주소에 데이터를 저장하는 자료구조입니다. 각 값들은 연속된 주소에 위치하므로 인덱스를 사용하여 빠르게 접근할 수 있습니다.
하지만, 연결 리스트는 배열과 달리 중간 값을 인덱싱하여 바로 접근하는 것이 불가능합니다. 연결 리스트의 탐색은 보통 헤드로부터 시작하여 각 노드가 가리키는 다음 노드로 이동하며 이루어집니다.
이런 특성 때문에 연결 리스트는 노드의 삽입과 삭제가 빈번한 경우에 유용하지만, 특정 요소를 검색하는 데는 시간이 더 걸릴 수 있습니다.
연결리스트 특징
배열에 비해 연결 리스트의 장점
-
동적 메모리 할당: 연결 리스트는 실행 중에도 데이터 크기를 유연하게 조정할 수 있어, 미리 데이터 크기를 알 필요가 없습니다.
-
삽입/삭제 용이: 중간에 있는 요소를 삽입하거나 삭제할 때, 연결 리스트는 포인터만 조정하면 되므로 상대적으로 간편합니다.
-
메모리 효율: 연결 리스트는 불필요한 메모리를 미리 할당하지 않아 메모리 사용 효율성이 높습니다.
-
데이터 타입의 다양성: 연결 리스트는 다양한 타입의 데이터를 한 리스트 안에서 저장할 수 있어, 유연성이 높습니다.
배열에 비해 연결 리스트의 단점
-
메모리 사용 비효율: 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터도 저장해야 해서 추가적인 메모리를 필요로 합니다.
-
코드 복잡성: 연결 리스트를 사용하면 삽입과 삭제를 위해 추가적인 코드가 필요하므로 배열에 비해 코드가 복잡해질 수 있습니다.
-
시간 복잡도: 특정 요소를 찾는데 있어서는 배열에 비해 시간이 더 걸릴 수 있습니다.
수행시간 관점
- 배열은 삽입 또는 삭제 시 데이터 이동이 필요하지만, 연결 리스트는 포인터만 변경하면 되므로 작업이 더 빠릅니다.
- 연결 리스트는 삽입과 삭제 연산이 빈번할 때 효율적입니다.
- 그러나 연결 리스트는 특정 요소를 찾을 때 전체를 순회해야 하므로, 검색 시간이 느립니다.
따라서, 삽입과 삭제가 중요한 경우에는 연결 리스트를, 검색이나 랜덤 액세스가 중요한 경우에는 배열을 사용하면 좋습니다.
연결리스트 연산
검색
배열처럼 특정 원소의 인덱싱이 불가능하기 때문에 head값부터 비교하여 값을 찾는 모습
수행시간은 O(n)
삽입
삭제
배열의 삽입 삭제는 최악의 경우 삽입되는 원소 나머지 원소들을의 위치를 재조정해야하므로
O(n)이 됩니다.
하지만 연결리스트는 삽입 삭제만 수행시간을 보면 O(1)이 됩니다.
하지만 삽입 삭제하고자 하는 값을 탐색하는 수행시간도 생각해야 합니다.
참고 출처
