리스트란 데이터를 일렬로 나열한 것을 추상화 한 것이다. 목록이나 도표가 그 예이다.

리스트의 구현방법으로는 두 가지가 있다.

1) 배열

 배열로 구현된 리스트는 구현이 쉽다는 장점이 있다. 바로 옆에 데이터가 붙어 있기 때문에 검색에 유리하다. 하지만 배열을 미리 선언해야 하기 때문에 메모리 활용이 비효율적이다라는 단점이 존재한다. 또한 삽입 삭제시 아이템들의 위치를 모조리 이동시켜야 하기 때문에 많은 시간이 소요된다.

2) 연결리스트

 반면 연결리스트는 배열로 리스트를 구현하는 것보다 다소 복잡하지만 메모리 공간 활용에 있어서 매우 효율적이다. 그리고 삽입 삭제 시에도 시간 면에서 유리하다.

리스트를 삽입 삭제 할 때는 다음과 같은 순서에 따라 작업이 진행된다.

• 기본

• 삽입

• 삭제