🔗 연결 리스트?

연결 리스트(linked list)는 객체가 선형적 순서를 가지도록 배치된 자료구조다. 인덱스에 의해 선형적 순서가 결정되는 배열과는 달리 연결 리스트에서는 각 객체에 있는 포인터에 의해 순서가 결정된다.

양방향 연결 리스트

• key 속성값과 두 개의 포인터인 prev와 next를 속성값으로 가지는 객체다.
• 리스트의 원소 x가 주어질 때, x.next는 연결 리스트의 바로 다음 원소를, x.prev는 바로 직전 원소를 가리킨다.
• x.prev = NIL 이라면 이전 원소가 없으므로 이 리스트의 첫 번째 원소 또는 head라 한다.
• x.next = NIL 이라면 원소 x는 바로 다음 원소가 존재하지 않으므로 이 리스트의 마지막 원소 또는 tail이라고 한다.

단순 연결 리스트: prev 포인터가 제외된 리스트다.

연결 리스트에서의 검색

Search 프로시저는 단순 선형 검색을 통해 리스트 L에서 키 k를 가지는 첫 번째 원소를 찾아 그 포인터를 리턴한다. 키 k를 갖는 원소가 존재하지 않으면 NIL 값이 리턴된다.

Ex)
L = [9, 16, 4, 1]

리스트 L의 값이 다음과 같을때 Search(L, 4) 프로시저를 호출하면 세 번째 원소의 포인터를 리턴한다.

n개의 원소를 가지는 리스트를 검색할 때 최악의 경우 리스트의 모든 원소를 검색해야 하므로 O(n)의 수행시간이 걸린다.

연결 리스트로의 삽입

Insert 프로시저는 key 속성이 미리 채워진 원소 x를 연결 리스트의 맨 앞에 이어붙인다.

n 개의 원소를 가지는 리스트에 대해 Insert 프로시저의 수행시간은 O(1)이다.

연결 리스트에서의 삭제

Delete 프로시저는 연결 리스트 L에서 원소 x를 삭제한다. 이를 위해서는 원소 x의 포인터가 필요하고, 이후 포인터를 갱신하여 원소 x를 리스트로부터 떼어놓는다. 주어진 키를 가지는 원소를 삭제하려면 우선 삭제하고자 하는 원소의 포인터를 얻기 위해 Search를 호출해야 한다.

n 개의 원소를 가지는 리스트에 대해 Search 프로시저의 수행시간은 O(1)이지만 주어진 키를 가지는 원소를 삭제하려면 O(n)의 수행시간이 필요하다.