※ 데이터를 구조화 시키는 가장 기본적인 방법은 나열하는 것이다. 이렇게 나열한 목록을 리스트라 한다.
자료구조에서는 데이터를 구조화시키는 기본 표현 방식으로 순차 자료구조 방식과 연결 자료구조 방식이 있다.
선형 리스트란??
리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트를 선형리스트(Linear List) 또는 순서 리스트(Ordered List)라고 한다.
(내가 코딩하면서 쓰는 기본적인 리스트들을 지칭한다... 메모리에 저장하는 물리적인 순서가 순차적으로 되어있다).
선형리스트에서 원소의 삽입과 삭제
1. 선형리스트에서 원소를 삽입하려면 삽입하려는 위치부터 그 뒤의 원소들을 모두 한칸씩 뒤로 옮긴다음 저장해야 된다.
- 선형리스트에서 원소를 삭제하려면 원소를 삭제하고 그 뒤의 원소들을 한칸씩 앞으로 옮겨줘야된다.
(원소의 삽입 삭제가 많은 데이터보다는 순차적으로 축적하는 데이터에 적합할 것으로 보인다)
1차원 배열의 순차표현
ex)선형리스트를 1차원 배열로 구현한 프로그램
public static void main(String[] args) {
int list[] = new int[]{157,209,251,312};
for(int i =0; i<list.length;i++){
System.out.println(list[i]);
}
}
2차원 배열의 순차표현
실제로 메모리에 저장될 때에는 1차원 순서로 저장이 된다.
물리적 저장 방법으로는 행 우선 순서(왼쪽) 방법과 열 우선 순서(오른쪽) 방법이 있다.
ex)선형리스트를 2차원 배열로 구현한 프로그램
public static void main(String[] args) {
int list[][] = new int[][]{
{63,84,140,130},
{157,209,251,312}
};
for(int i = 0; i<2 ; i++){
for(int j=0; j<4; j++){
System.out.print(list[i][j]+ ", ");
}
System.out.println();
}
}
3차원 배열의 순차표현
실제로 메모리에 저장될 때에는 1차원 순서로 저장이 된다.
물리적 저장 방법으로는 면 우선 순서(왼쪽) 방법과 열 우선 순서(오른쪽) 방법이 있다.
ex)선형리스트를 3차원 배열로 구현한 프로그램
public static void main(String[] args) {
int list[][][] = new int[][][]{
{{63,84,140,130},
{157,209,251,312}},
{{59,84,130,135},
{149,187,239,310}}
};
for(int i = 0; i<2 ; i++){
for(int j=0; j<2; j++){
for(int k=0; k<4; k++){
System.out.print(list[i][j][k] + ", ");
}
System.out.println();
}
System.out.println();
}
}
※순차 자료구조는 원소들의 순서를 따로 표시할 필요없이 간단하게 구성할 수 있고, 인덱스를 사용하여 특정 원소를 쉽게 접근할 수 있다.
그러나 원소 삽입과 삭제시에는 물리적으로 원소를 뒤로 밀어내거나 앞으로 당겨서 순서를 유지해야 되므로 추가적인 오버헤드가 발생한다. 삽입, 삭제 연산이 많이 필요한 많이 필요한 문제에서 순차 자료구조를 사용하는 것은 비효율 적이다.
결론) 변화가 거의 없고 순차적으로 저장하는데 사용하는것이 적합하다.
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 02-2 단순 연결 리스트 (0) | 2016.11.25 |
|---|---|
| 02-1 연결 자료구조 방식 (0) | 2016.11.25 |
| 01-3 행열의 순차 자료구조 표현 (0) | 2016.11.25 |
| 01-2 다항식의 순차 자료구조 표현 (0) | 2016.11.25 |
| 자료구조 시작! (0) | 2016.11.25 |
