자료구조는 데이터 값의 모임이다.
자료구조는 원소들의 사이의 관계가 논리적으로 정의된 규칙에 의해서 나열이 된다.
즉, 데이터를 효율적으로 저장하고 관리하기 위한 방법을 말한다.
이번 포스트에서는 여러 자료구조 중 배열과 리스트에 대해서 알아보겠다.
배열(Array)
배열은 물리적 메모리의 연속 공간에 값이 채워져 저장이 될 수 있는 자료구조이다.
즉, 메모리상의 주소에 연속적으로 값이 저장이 되는 것이다.
배열은 선언한 자료형의 값만 저장할 수 있다.
예를 들어 숫자를 자료형으로 선언한다면 그 배열에는 오직 숫자만 저장을 해야 한다.
배열은 인덱스 값이라는 것이 있다.
이 인덱스 값은 배열에 담겨 있는 값을 접근하고 식별하는데 사용한다.
인덱스 값은 고유한 값이며 1부터 시작이 아니라 0부터 시작을 한다.
예를 들어 1부터 5까지 값이 담긴 배열이 있다면 인덱스의 값은 0부터 4인것이다.
만약 배열에 첫 번째에 들어가 있는 값인 1을 접근하기 위해서 인덱스 값 1을 넣는다면 두 번째에 저장이 되어 있는 2가 나올 것이다.
자바의 경우 배열의 크기를 지정할 수 있는데 한 번 지정을 하게 되면 크기를 줄이거나 늘릴 수 없다.
배열은 인덱스를 통해서 각 요소에 접근을 하기 때문에 빠른 접근이 가능하다.
하지만 중간에 요소를 추가하거나 삭제할 때는 속도가 느리다.
그 이유는 배열은 값이 순차적으로 저장되어 있는 자료구조이다.
그렇기 때문에 어떤 한 값이 추가가 되거나 삭제가 되면 그 뒤에 있는 값들을 모두 한 칸씩 뒤로 물리거나 앞으로 당겨주어야 한다.
그래서 배열은 데이터의 크기가 고정이 되어 있거나 빠른 접근을 해야 하는 경우에 사용하는 것이 좋다.
또 배열의 경우 데이터의 크가가 고정이 되어 있어서 메모리를 할당 후 추가적으로 사용하지 않는다.
리스트(List)
리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조이다.
리스트를 이해하기 위해서 노드라는 것을 알아보자.
노드는 리스트를 구성하는 기본 단위이다.
이 노드들이 연결이 되어서 리스트를 구성하는 것이다.
이 노드는 데이터와 포인터로 구성이 되어 있다.
데이터는 노드에 저장을 하고자 하는 값이다. 포인터는 다음 노드를 가르키는 메모리 주소가 저장이 되어 있다.
리스트는 각 노드들이 메모리의 불연속적으로 저장이 되어 있다.
그래서 포인터로 다음 노드의 메모리 주소를 넣어준다.
이 메모리 주소를 연결 시켜서 하나의 리스트를 만들어 준다.
이러한 포인터를 통해서 리스트의 노드 값을 논리적으로 연결을 시켜준다.
리스트는 배열처럼 크기를 지정해주지 않아도 된다.
리스트는 중간의 값을 추가하거나 삭제할 때 유용하다.
먼저 새로운 노드를 만들어준다.
그리고 연결하고자 하는 위치의 전 노드의 포인트 값을 새로운 노드가 저장되어 있는 메모리 주소 값으로 변경을 해준다.
그리고 새로운 노드의 포인터 값에 넣고자 하는 위치의 다음 노드의 메모리 값을 넣어주면 중간에 추가가 가능하다.
배열처럼 중간에 삽입을 할 때 모든 값을 뒤로 한 칸씩 미루거나 당겨주는 것을 할 필요없이 포인터의 값만을 변경해서 추가, 삭제가 가능하다.
하지만 어떤 값에 접근을 할 떄는 느리다.
그 이유는 메모리에 불연속적으로 저장이 되어 있기 때문에 첫 번째 노드부터 하나씩 차근차근 찾아가야 하기 때문이다.
그리고 데이터의 값과 다음 노드의 메모리 주소를 저장하는 포인터 값을 저장하기 때문에 메모리를 차지하는 크기가 상대적으로 크고 구조 복잡하다.
