[CS] 자료구조 2. 연결리스트

 

연결리스트

연결리스트의 구조는 빼빼로처럼 생겼다고 생각하면 받아들이기 쉬웠다. 

먹고 싶은 부위인 초콜릿엔 필요한 값을 넣고, 그냥 과자 부분엔 포인터를 넣는다. 

이 포인터에는 다음 값이 어디 저장되어있는지 주소를 저장한다. 

하나의 빼빼로를 노드라고 부른다. 

추가 

연결리스트에서 노드를 집어넣기 위해서는 2가지 일만 해주면 된다. 

• 이전 노드의 포인터를 집어넣으려는 노드의 주소로 지정한다. 
• 다음 노드의 주소를 집어넣으려는 노드의 포인터로 지정한다.

확실히 배열과는 다른 차이가 있다. 

시간이 길이에 상관되지 않는 상수값이기 때문에, O(1)의 시간 복잡도를 가진다고 한다. 

 

조회 

조회가 연결리스트의 단점이다.

5개의 노드가 연결된 리스트가 있다고 생각했을 때

원하는 값을 찾기 위해서는 모든 노드를 포인터의 지시에 따라 

내가 원하는 값을 찾을 때 까지 이동한다. 

즉, 조회에 걸리는 시간이 1이 될수도, n이 될수도 있다. 

노드를 찾는데 걸리는 시간의 평균이 (n+1)/2가 되며, O(n)의 시간복잡도를 가진다고 말할 수 있다. 

 

삭제

조회를 통해 하나의 노드를 찾았다면, 이를 삭제하는 방법은 이전 노드의 포인터에 삭제 노드의 포인터에 있는 주소를 담아주면 땡이다. 

시간이 O(1)의 시간 복잡도만을 가지게 된다. 

 

총평

추가와 삭제가 아주 수월하지만, 조회에서 시간이 많이 걸리게 된다. 

나중에 보는 비선형 자료구조에서 트리는 똑같은 노드를 쓰면서 더욱 시간을 효율적으로 쓰는 방법으로 발전된 것 같다. 

비선형이 되어버린(?) 이유를 찾을 수 있던 것 같다. 

 

또한, 알고리즘을 풀면서 리스트와 배열을 구분하여 쓸 필요가 확실히 있다고 생각한다. 

예를 들면 DP문제를 푸는데, 주어진 데이터를 연결리스트로 저장해버리면, 데이터를 조회해 연산하는 과정에서

시간이 무지하게 쓰일 것 같다.