영암사는 승경이네

1. 개요

 - List에 대해 알고, 배열과 연결리스트의 개념과 차이를 이해한다.

2. 리스트(List)란?

 - 순서가 의미를 갖는 데이터들의 집합이다.

 - 삽입, 삭제, 검색 등의 기본적인 연산이 가능한 자료구조이다.

 - 리스트를 구현하는 대표적인 두가지 방법은 배열과 연결리스트이다.

즉, 리스트란 첫번째에는 A가, 두번째에는 B가 세번째에는 C가 들어있는 것처럼 순서마다 특정 데이터를 갖고 있고, 이 순서를 통해 삽입, 수정, 삭제, 검색을 할 수 있는 자료구조를 말한다.

3. 배열이란?

 - 같은 종류의 데이터들이 메모리상에 순차적으로 저장되어 있는 자료구조이다.

 - 같은 종류의 데이터들이기때문에 각각 데이터들의 크기가 같고, 메모리상에 순차적으로 저장되어 있기 때문에 주소 값 계산이 쉽고, 랜덤 액세스가 가능하다.

 - 조회할때는 빠르나 중간 데이터를 삭제, 추가 시에는 시간이 많이 걸린다.

 - 배열의 구조는 다음과 같다.

 - int 형은 정수형 자료형으로 4Byte이다. 주소를 보면 4byte 간격이란 것을 알 수 있다. 내가 배열의 5번째 값을 조회하고 싶다면 처음 주소 값에서 자료형 크기 * 5 해준 값(주소값)을 구한 후 바로 접근하면 된다. 즉, 배열에서 특정 데이터를 조회하려면 자료형과 인덱스를 통해 주소 값 계산 후 바로 접근한다. (참고로 이 방식이 랜덤 액세스 방식이다.) 대신 중간에 데이터를 추가하거나 삭제 한다면 빈 자리를 매꾸기 위해 아주 많은 데이터들이 움직여야한다. 예를들면, 3번째 인덱스에 위치한 4000 값을 삭제한다면, 5000이 그 그 자리로 이동해야하고, 5000 자리로는 6000이 이동해야하고... 이게 끝까지 반복되어야한다. 만약 100000개 크기의 배열에서 1번째 값을 삭제한다면 100000-1번 움직여야한다.

4. 연결리스트

 - 같은 종류의 데이터들이 메모리상에 비순차적으로 저장되어 있는 자료구조이다.

 - 크기의 제한이 없다.

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

 - 랜덤 엑세스가 불가능하다.

 - 연결리스트의 구조는 다음과 같다.

 - 연결리스트의 값에는 총 2가지 정보가 들어간다. 하나는 메모리 주소에 해당하는 데이터. 하나는 다음 주소 값이다. 그리고 이 주소 값을 거칠때마다 인덱스가 증가한다. 예를들어 이 연결리스트의 2번째 인덱스에 해당하는 값을 조회하려면 시작주소인 00ffff00에 저장된 다음 주소인 00ffff08이 된다. 만약 100000개 크기의 연결리스트에서 100000번째 값을 조회하려면 주소 계산이 되지 않기 때문에 무작정 메모리 시작주소부터 다음 주소를 100000번 까야한다. 즉 조회에 시간이 오래걸린다. 대신, 어떤 값을 삭제하거나 추가할때에는 메모리를 찾은 후 다음주소만 바꿔주면 되기 때문에 배열에 비해 시간이 적게 걸린다. 예를들어 3번째와 4번째 사이에 3500을 추가하고싶다면 먼저 3번째 주소를 찾은 후(00ffff18) 메모리 빈 공간(00ffff10)에 3500값을 만들고 3500의 다음 주소를 3번째 인덱스의 다음 주소로 저장한다. 그리고 3번째 인덱스의 다음 주소에는 3500값의 주소로 저장한다.

5. 마치며

 가려운 등이 긁힌 느낌이다.. java에서 왜 배열 길이를 선언하고 후에 못늘리는지,(메모리에 순차적으로 들어가기 때문에 나중에 길이를 늘리게 되면 현재 다른 데이터를 위해 할당된 메모리 주소를 침범할 수 있기 때문) 굳이 길이 제한이 없는 ArrayList같은 연결리스트를 놔두고 왜 배열을 쓰는지 (랜덤 액세스로 조회 시간이 엄청 짧음), 그리고 이 둘의 차이, 메모리 구조 등을 확실히 이해할 수 있는 좋은 공부였다. 너무좋다...ㅎㅎ