[자료구조] List - 02

이번에는 List 중 Linked list에 관한 글이다.

1. Linked list ?

Linket list는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다. Node는 데이터 값과 next node 주소값을 저장한다.

Linked list는 메모리상에서 비연속적으로 저장돼 있지만, 각각의 node가 next node의 메모리 주소값을 가리키기 때문에 논리적으로 연속성을 갖는다.

# 물리적으론 비연속, 논리적으론 연속?

각 node는 데이터 저장뿐만 아니라, next node의 address 정보도 갖고 있기 떄문에 논리적으로 연속성을 유지하며 연결된다. Array의 경우 연속성을 유지하기 위해 메모리상 순차적으로 데이터를 저장하는 방식을 사용하지만, Linked list에는 메모리상 연속성을 유지할 필요 없기 때문에, 메모리 사용이 좀 더 자유롭다. 하지만 next node의 address를 추가적으로 저장해야 하기 때문에 데이터당 메모리 차지가 더 커진다.

2. Operations

Linked list에는 여러 가지 기능이 있다

- get( )
: 저장돼 있는 값을 반환
- insert_back( )
- insert_front( )
- insert_at( )
: 데이터를 추가
- remove_back( )
- remove_front( )
- remove_at( )
: 데이터를 삭제
.
.
.