연결리스트의 개념과 기본연산 1

리스트

 

기본적인 연산 : 삽입, 삭제, 검색 등

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

 

배열의 단점

 

크기가 고정 - reallocation이 필요

리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 함

 

연결 리스트

 

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

길이의 제한이 없음

하지만 랜덤 액세스가 불가능

랜덤 액세스란 배열의 경우에는 배열의 10번째 데이터를 읽어야한다면

a[10] 하면 되지만 어떤 칸에 읽는데 걸리는 시간이 거의 동일하다.

연결리스트는 10번째 데이터를 읽고 싶다면 

첫번재 데이터부터 순서대로 가야만 한다.

 

어떤 데이터와 나의 다음데이터의 주소의 데이터 쌍을

노드라고 부른다.

첫번째 노드의 주소는 절대 잃어버려서는 안된다.