연결 리스트

연결리스트(Linked List)

각 노드가 한 줄로 연결되어 있는 자료 구조

각 노드는 (데이터,포인터) 형태를 가진다.

포인터 : 다음 노드의 메모리 주소를 가리키는 목적으로 사용된다.

연결성 : 각 노드의 포인터는 다음 혹은 이전 노드를 가리킨다.

 

 

연결 리스트 vs 배열

배열(Array)
- 특정 위치 데이터 삭제
배열에서는 특정 위치의 데이터를 삭제할 때 O(n) 시간이 소요됩니다.
이는 삭제 후 나머지 요소들을 한 칸씩 이동시켜야 하기 때문입니다.

- 데이터 삽입
배열에서 특정 위치에 데이터를 삽입할 때도 O(n) 시간이 소요됩니다.
이는 삽입할 위치 이후의 요소들을 한 칸씩 이동시켜야 하기 때문입니다.

 

연결 리스트(Linked List)

- 특정 위치 데이터 삭제
연결 리스트에서는 특정 위치의 데이터를 삭제할 때 O(1) 시간이 소요됩니다.
단, 삭제할 노드의 이전 노드를 알아야 하며, 연결만 끊어주면 됩니다.

 

- 데이터 삽입
연결 리스트에서 특정 위치에 데이터를 삽입할 때 O(1) 시간이 소요됩니다.
삽입할 위치를 알고 있다면 물리적인 위치를 옮기지 않고도 삽입이 가능합니다.