연결 리스트란?
연결 리스트란 노드라는 구조체로 이루어진 선형 자료구조이다.
연결 리스트는 배열과의 차이점에서 많이 질문이 나올 수 있는 자료구조이다. 이 차이는 메모리 구조의 차이에서 발생하고, 그로 인해 서로의 장/단점이 갈리게 된다.
구조
앞서 작성한 것 처럼, 연결 리스트는 배열과 메모리 구조에서 차이를 보인다. 배열은 메모리에 공간을 할당받고, 각 데이터들이 물리적으로 연속성을 띈 채로 저장이 된다. 하지만 연결 리스트는 그렇지 않다.
연결 리스트는 노드(Node)라는 구조들로 이루어져 있다. 노드는 자신이 가리키는 데이터와 다음 순서의 노드의 주소를 지니고 있다.
이 점으로 인해서 메모리에서 물리적으로 연속적일 필요가 없기 때문에, 메모리 공간을 더 효율적으로 사용할 수 있고, 노드들이 서로 다음 노드를 가리키는 것으로 논리적 연속성을 보여준다.
동작
연결 리스트에서의 각 동작에 대한 시간 복잡도를 작성하고, 그 이유에 대해서 작성한다.
| 행동 | 시간 복잡도 |
|---|---|
| 조회 | O(n) |
| 검색 | O(n) |
| 삽입 | O(1) |
| 삭제 | O(1) |
조회
조회의 경우 연결 리스트는 순차 접근(Sequencial Access)을 해야 하기 때문에 특정 인덱스까지 가기 위해선 그 만큼의 노드들을 거쳐 가야 하기 떄문에 O(n)의 성능을 보인다.
검색
검색의 경우 다른 선형 자료구조들과 마찬가지로 노드들을 순회하면서 데이터가 맞는지 체크해야 하기 때문에, O(n)의 성능을 보인다.
삽입
삽입의 경우 연결 리스트는 연결된 노드의 주소만을 변경해주면 되기 때문에, O(1)의 성능을 보인다.
이때 O(1)의 성능을 서로 연결을 바꾸는 행위에 대한 성능을 뜻하며, 특정 인덱스에 삽입하기 위해선 조회가 이루어져야 하기 때문에, 실질적으로는 O(n)의 성능을 보인다.
삭제
삭제 역시 삽입과 마찬가지의 이유로 O(1)의 성능을 보이고, 실질적으로는 O(n)의 성능을 보인다.
