◆◆ Array 와 Linkedlist : 같은 타입의 여러가지 요소 (집합) 를 저장
◆ 1. Array
㉠ 정의
index 와 index에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.
즉, 동일한 자료형이고 메모리상에 연속적으로 놓인 데이터를 일괄적으로 처리하기 위해서
만든 하나의 집합 형식으로 묶어놓은 자료 구조이다.
㉡ 특징
메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.
메모리 관리면에서 공간의 낭비가 심하다.
자료의 삽입및 삭제가 어렵다.
◆ 2. Linkedlist
㉠ 정의
연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하
는 자료 구조이다.
이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게
된다.
㉡ 특징
메모리 할당이 비연속적이며, 크기가 동적이므로 낭비가 없다.
보통 element 와 element 를 가로 질러서 조건에 맞을 때까지 순차 검색하므로 검색이 느리다.
자료의 삽입및 삭제가 쉽다.
㉢ 종류
가. 단순 연결 리스트 : 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가르킴
나. 이중 연결 리스트 : 단순 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가
리킴
다. 원형 연결 리스트 : 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조
◆◆ 3. Arrays and linked lists 중 어떤 것을 사용할지 결정하기 (중요!!)
㉠ 사이즈 면에서....
Arrays 은 사용자의 필요에 따라 1차 혹은 다차 원으로 구현할수 있다.
linked lists 는 태생적으로 1차원이며, 각각의 요소(element)들은 이전 요소와 다음 요소의 포인터를 가지고 있다.
㉡ 할당 면에서....
Arrays는 만들어질때부터 사이즈가 정적으로 정의 된다. 게다가 Arrays에서 메모리 할당은 인접하며 끊어지지 않는다.
>>>> Contiguous Memory Allocation - 연속 메모리할당 (프로세스들에게 연속된 메모리 공간을 할당해 주는 것)
그러므로 Arrays는 디자인할 당시에 요소(element)의 최대 숫자를 알고있을 때 전형적으로 사용된다.
이러한 접근방식으로 구현한 배열 단점은 커다란 배열은 아마도 사용되지 않는 큰 메모리가 필요로 한다는 것이다.
특히나 이렇게 요소의 최대값으로 디자인된 배열은 종종 그들의 용량에 비해 턱없이 작게 저장되기도 한다.
그리고 오래된 os 를 가진 초소형 장치들과 같은 경우에 메모리 제약이 당신이 사용할수 있는 배열의 크기를 제한할 수도 있다.
반면에, linked lists 는 보통 동적이다. 실시간으로 필요할 때 마다 줄이거나 키울 수 있다.
이러한 특징들로 인해서 linked lists 는 요소의 수를 몰랐을 때 좀더 효과적으로 사용될 수 있다.
뿐만아니라 메모리가 요소요소에 의해 할당되므로, 비연속적이다.
이런 불확실성을 다루는데서 오는 단점은 linked lists에서 추가하거나 지울때에 미리 할당된 배열된 요소들의 값을 정의할때 보다
좀더 부하가 있다 라는 것이다.
그러나 linked lists에 얼마나 많은 메모리가 할당될 것이냐에 대한 유일한 제한은 당신의 목적에 의해서 사용하는 힙메모리의 크기
에 의해서 결정되어진다.
㉢ 요소를 접근하는 방식에 있어서....
Arrays 안에 있는 요소들은 그들의 인덱스를 통해서 접근할 수 있다. 그러므로 데이터 접근은 찾을 요소를 알면 빠르고 쉽다.
만약 요소의 인덱스를 모르고 어떤 키값에 의해서 정렬되어있을 경우에 보다 효율적으로 특정 요소를 찾아낼 수 있다.
이러한 알고리듬은 특정 요소가 위치하는 비교 의 최소값만을 허락하며,
Arrays를 병합하거나 정렬하는 효율적이고 안정적인 몇가지 알고리듬들이 존재한다.
그러나 Arrays는 요소의 순서가 쉽게 변할 때 비효율적이다. 요소가 자주 지워지거나 삽입되는 배열을 관리할 경우에 배열의 모든
요소를 옮겨나를 필요가 있다.
반면에, linked lists는 보통 요소와 요소를 가로 질러서 조건에 맞을 때까지 검색한다.
왜냐하면 linked lists 에 대한 메모리는 연속적이라고 보장할 수 없기 때문이다.
이러한 검색방법은 (인덱스와 같은 다른 데이터 구조체를 포함하지않는) 리스트를 검색하는 유일한 방식이다.
비연속 메모리의 윗쪽부분은 리스트를 다시 정의하는 것으로, 단순히 링크를 조정하는 것을 포함한다.
요소의 삽입과 삭제는 포인터 수정을 필요로 하고 실제적인 데이터의 전송은 전혀 필요로 하지 않는다.
㉣ 규칙들을 깨는 것
거의 모든 언어에서 두가지 방식을 모두 지원을 한다.
C에서 변수나 객체를 가르키는 포인터는 만약 그 포인터가 할당된 배열 안에서 첫번째 요소를 가르킬 때 배열처럼 사용할 수 있다.
이렇게 포인터를 배열처럼 사용할 때 이 포인터의 크기조절이 필요하면,
realloc() 라는 펑션이 메모리의 새로운 블럭을 할당하고 새로운 위치로 존재하는 모든 요소를 옮긴다.
이러한 기법은 연속적인 메모리 할당 과 요소 인덱싱을 유지하는 가운데 배열의 동적인 리사이징을 가능하게 한다.
Java 에서는 제공되는 linked-list class 가 인덱싱 되는 기법 뿐만아니라 top, next, previous, etc. 과 같은 표준 리스트 메서드를
모두 지원한다.
indexOf(), get(), and set() 과 같은 메서드들은 리스트의 요소가 흡사 배열과 같이 엑세스 되도록 도와준다.
게다가 Java는 리스트 클래스의 향상된 리사이즈가능한 배열을 나타내는 "ArrayList class " 를 제공한다.
이 두가지 클래스 모두 그들의 리스트 표현방식에서 실제 배열로 변환되는 메서드를 지원한다.
프로그래밍 언어가 갈수록 진화되고있고 두가지 구조체의 구분이 점점 모호해지고 있다.
하지만 어디서 이러한 구조체들이 고안되었는지 그리고 새로운 클래스안에서 어떻게 쓰여지고 있는지 기억하는것은 항상 중요하
다.
이러한 새로운 개선들은 프로그래머에게 자세한 부분을 숨기곤 함에도 불구하고, 요구되는 컴퓨터적인 부하 와 자원들은 변하지
않는다.
㉤ 결정내리기....
만약 당신의 데이터가 다차원적인 구조체로 표현이 되어지거나, 요소들의 숫자를 미리 알게 되거나, 일관된 성질을 가지고 있다면
array 가 제일 좋다.
만약 당신의 데이터가 1차원으로 쉽게 표현이 된다거나, 요소의 숫자들을 알지 못한다거나, 목적상 데이터가 자주 변한다고 생각
이 되어질거라 예상될 때라면 linked lists 가 좀더 효율적이다.
만약 당신의 데이터가 자주 검색되거나 접근되고 수정이 잦질 않다면 array 가 당신이 기대하는 운영에서 최소의 부하를 제공한다.
만약 당신이 정기적으로 요소를 추가하거나 제거할때, 특별히 정렬된 순서를 그대로 유지할 필요가 있을 때 linked lists를 사용하
는 것이 낫다.
결국엔 당신의 데이터 와 당신의 운영면에서의 필요가 당신의 목적에 어떤 구조체가 최선인지 결정할 것이다.
원문:
http://articles.techrepublic.com.com/5100-10878_11-1050183.html
'자료구조' 카테고리의 다른 글
| 자료구조(해싱) (0) | 2009.11.06 |
|---|---|
| 자료구조(Stack 과 Queue) (0) | 2009.11.06 |