자료구조 - 연결 리스트 (Linked List)

1. 연결 리스트란?

연결 리스트(Linked List)란 불연속적 메모리 공간에 데이터를 빈틈없이 저장하며 노드를 연결하여 만든 리스트로 첫 번째 노드를 헤드, 마지막 노드를 테일이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다. 크기가 고정되어 있지 않아 크기 제한에서 자유롭다. 인덱스 접근이 불가능하다.

 

2. 시간 복잡도

1) 삽입

- 리스트의 맨 앞/뒤에 삽입하는 경우 : O(1)

- 리스트의 중간에서 삽입하는 경우 : O(n) (탐색)

 

2) 삭제

- 리스트의 맨 앞/뒤에 삭제하는 경우 : O(1)

- 리스트의 중간에서 삭제하는 경우 : O(n) (탐색)

 

3) 탐색

- O(n)

 

3. 장단점

1) 장점

- 포인터로 연결되어 있어 포인터가 가리키는 노드만 변경하면 되기 때문에 삽입과 삭제가 용이하다.

- 크기가 정해져 있지 않고 동적으로 생성된다

- 연속적인 메모리 할당이 필요없다.

- 사용한 메모리를 재사용할 수 있다.

 

2) 단점

- 원소를 탐색할 때 임의의 접근은 불가능하기 때문에 느림

- 포인터를 위한 추가 공간이 필요하며 프로그램 작성이 어려움

 

4. 응용

- 크기가 정해져 있지 않을 때

- 삽입과 삭제가 자주 일어날 때

- 검색을 자주 하지 않을 때