List (리스트)

List 란?

 

리스트는 정보 저장을 위한 가장 흔한 자료구조중에 하나이다.

Lists are one of the most common data structures for storing information.

 

사용 예시 )) 게임에서 사용자의 인벤토리창, 진찰을 대기하는 환자들

 

 

간단한 리스트는 기본자료형 Array 로 표현이 가능하다. ( Array 는 Linear list 이다.)

A simple list can be represented by an array of primitive data types.

 

 

 

Arrays as lists

 

 

 

하지만 Array 와 List 의 차이는 꼭 알고 넘어가야 한다.

 

 

Array 

- 인덱스로 (indices) 조회를 하여 조회가 빠르다.

- Contiguous memory(연속 메모리) 할당으로 순서대로 접근 할떄도 빠르다.

- 구현이 쉽다.

- 정적인 표현

 

단점 

1. Insert, delete 시 뒤 요소들을 모두 이동해야한다( 비효율 )

2. 한번 크기를 선언하면 변경이 안된다.

3. 메모리 재사용이 불가능하다. ( 한번 사이즈를 8로 할당했다면 안에 데이터가 꽉 차있지 않더라도 메모리를 8 만큼 계속 차지하고있다.)

 

언제 사용해야 할까?

-> 데이터 크기가 정해저있고 Insert, delete 이 일어나지 않을때 최고의 효율을 보여줌.

 

 

 

List

- Insert, delete 이 효율적이다. ( 노드를 이용한 참조 관계만 수정하면 되기때문)

- 크기가 flexible 하다.( 변형가능 )

- 메모리 재사용 가능.

- 불연속적 메모리 할당. ( 포인터를 통한 접근 )

- 동적인 표현

 

단점

1. 구현이 복잡하다

2. 검색이 비효율적이다 (처음부터 순차적으로 노드를 따라가면서 찾아야한다.)

 

언제 사용해야 할까?

-> 데이터 크기가 정해져있지 않고 Insert, delete 이 빈번할때 또는 검색이 적은경우.