리스트 (LIST)

[ 리스트 ]

- 순서대로 자료를 저장하는 자료구조 (노드라는 개념이 존재한다)

- 메모리 공간이 필요에 따라 자유

- 기본적인 연산 삽입(insert) , 삭제(remove), 검색(search) 등

- 여러 개의 자료가 한 줄로 연결된 구조를 다른 말로 선형구조라고 한다.

- 리스트를 구현하는 대표적인 두 가지 방법 : 배열, 연결리스트

 

[ 배열의 단점 ]

- 크기가 고정되어 있어 reallocation 이 필요하다.

- 리스트의 중간에 어떠한 데이터를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다.

 

[ 연결리스트 ]

- 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며, 길이의 제한이 없다.

- 그러나 랜덤 엑세스가 불가능하다. ( n 번째 데이터를 읽어야 할 때.. 처음부터 순서대로 찾아야한다. )