자료구조 수업에서 배열과 함께 처음 배우는 가장 기본적인 자료구조이다. 설명은 생략.
다음 노드의 포인터만 갖고 있느냐 이전 노도의 포인터도 갖고 있느냐에 따라서, 단일 링크드 리스트와 양방향 링크드 리스트로 구현할수 있다. 맨 앞 노드와 맨 뒤 노드를 연결해서 서큘러 링크드 리스트를 사용하는 경우도 있다.
기본 라이브러리에 양방향 링크드 리스트가 제공되는 언어도 있긴 한데, 파이썬에서는 제공되지 않는다.
다행히도 PS에서 연결리스트를 요구하는 문제는, 거의 다 연결리스트를 안 쓰고 다른 방법으로 푸는 것이 가능하다!
구체적인 케이스를 보자. 연결리스트를 필요로 하는 문제는 리스트의 중간 위치에서 삽입과 삭제를 요구하는 문제들이다.
i번째 위치에 삽입/삭제를 반복하는 문제 / 현재 위치에서 i번째 뒤에 있는 원소를 삭제,삽입 하는 문제
연결리스트를 쓰면 삽입/삭제는 O(1)에 해결할수 있지만, 포인터를 i번째 까지 이동시키는데 O(n)이 걸려서 어차피 총 복잡도는 O(n)이다
차라리 그냥 배열을 쓰면, 삽입/삭제는 O(n)이지만 포인터를 이동시킬 필요가 없으니까, 총 시간복잡도는 마찬가지로 O(n) 이다.
굳이 연결리스트를 쓸 필요가 없다. 그냥 배열을 쓰자
Order Statistic Tree를 쓰면, n번째로 큰 원소를 찾는것과 그 원소를 삭제시키는 것을 모두 O(nlogn)에 할수 있으므로, 더 효율적으로 풀수 있는 문제들도 많이 있다
현재 위치를 이전 또는 다음 위치로 이동, 현재 위치에서 삽입이나 삭제를 반복
연결리스트를 쓰면 이 네가지 연산을 모두 O(1)에 처리 가능하다.
두개의 스택을 써서 똑같은 시간복잡도에 구현하는 방법이 있다.
현재 위치보다 앞에 있는 원소들을 l-스택에 모두 담고, 현재 위치보다 뒤에 있는 원소들을 r-스택에 모두 담는다. 현재 위치와 가까운 원소가 스택의 top에 있어야 하므로, r-스택은 순서가 뒤집힌 상태가 된다.
현재 위치를 왼쪽으로 이동할때는 l-스택에서 pop한 원소를 r-stack에 push하면 된다. 시간복잡도 O(1). 오른쪽으로 이동도 마찬가지.
삽입,삭제는 당연히 O(1)
-
환형 연결리스트에서 이러한 작업을 해야하는 문제의 경우는 덱을 이용해서 구현하면 된다.