연결 리스트(linked list): 실행 시간에 메모리를 할당하거나 해제할 수 있는 동적 자료 구조. 각 노드가 다음 노드에 대한 참조를 갖는 점이 특징이다.
단일 연결 리스트(Singly Linked list)와 이중 연결 리스트(Doubly Linked list)로 분리된다.
1. 단일 연결 리스트(Singly Linked list)
속성
- data: 연결 리스트 노드의 값(을 저장하는 속성)
- next: 다른 인스턴스(노드)에 대한 포인터(를 저장하는 속성)
연결 리스트의 시작을 헤드라고 부르며, (연결 리스트에 항목이 삽입되기 전) 헤드 속성의 기본 값은 null이다.
1) 삽입
헤드 자리에 값을 삽입하며, 기존의 헤드 노드를 새 노드의 next로 연결한다.
(헤드가 비어있는 경우, 헤드는 신규 노드로 설정된다.)
시간 복잡도
- O(1)
2) 값에 의한 삭제
삭제를 원하는 노드의 참조를 제거함으로써 구현한다.
삭제하고 싶은 노드(이하 a)가
- 연결 리스트의 중간일 때: a의 next 포인터가 가리키는 노드(이하 b)를 찾고, a의 이전 노드의 next 포인터가 b를 가리키도록 한다.
- 연결 리스트의 끝일 때: 마지막에서 두 번째 노드의 next 속성을 null로 설정한다.
시간 복잡도
- O(n)
(삭제 노드의 이전과 이후 노드를 찾아야 하기 때문에 최악의 경우 전체 연결 리스트를 순회한다.)
3) 헤드 항목 삭제
헤드에 헤드의 next 노드를 설정한다.
이 방식으로 연결 리스트를 사용한 스택을 구현할 수 있다.
시간 복잡도
- O(1)
4) 검색
모든 next 포인터를 반복 순회하여 검색한다.
시간 복잡도
- O(n)
2. 이중 연결 리스트
속성
- data: 연결 리스트 노드의 값(을 저장하는 속성)
- prev: 이전(헤드와 가까운 쪽) 인스턴스(노드)에 대한 포인터(를 저장하는 속성)
- next: 다음(테일과 가까운 쪽) 인스턴스(노드)에 대한 포인터(를 저장하는 속성)
양방향 단일 연결 리스트와 비슷하다.
리스트의 시작을 헤드 포인터라 부르고, 리스트의 끝을 테일 포인터라 부른다.
단 하나의 노드만 존재하는 경우 해당 노드는 헤드인 동시에 테일이다.
1) 삽입, 삭제
단일 연결 리스트의 삽입, 삭제와 비슷하나 이중 연결 리스트에서는 next 속성과 prev 속성이 함께 갱신되어야 하는 점이 다르다.
2) 헤드에 항목 삽입하기
단일 연결 리스트에서 헤드에 항목을 삽입하는 것과 비슷하나, prev 포인터를 갱신해야 하는 점이 다르다.
시간 복잡도
- O(1)
3) 테일에 항목 삽입하기
현재 테일인 노드를 테일의 prev에 연결하고, 새 노드를 테일의 next에 연결한다. 즉 새 노드가 테일이 된다.
시간 복잡도
- O(1)
4) 헤드의 항목 삭제하기
항목이 하나일 경우 헤드와 테일 모두를 null로 설정한다.
항목이 여러 개 존재하는 경우 현재 헤드를 헤드의 next 포인터로 설정한다.
이후 신규 헤드의 prev를 null로 설정한다.
이 방식은 큐 자료 구조의 dequeue 함수처럼 사용할 수 있다.
시간 복잡도
- O(1)
5) 테일의 항목 삭제하기
헤드 항목 삭제와 동일한 방식으로 삭제한다.
이런 방식 때문에 이중 연결 리스트는 양방향 큐 자료 구조와 비슷하게 사용될 수 있다.
시간 복잡도
- O(1)
6) 검색
next 포인터를 사용해 헤드에서부터 검색할 수 있고, prev 포인터를 사용해 테일에서부터 검색할 수도 있다.
이처럼 양방향으로 검색이 가능하기 때문에 완전 검색을 수행할 수 있다.
시간 복잡도
- O(n)
