03. 구조에 따른 분류
자료구조는 크게 선형, 비선형, 파일구조로 나눌 수 있습니다.
오늘은 선형과 비선형에 대해 간략히 적어보겠습니다.
선형 자료구조 (Linear)
선형(Linear) 즉, 데이터가 일정히 나열된 자료구조를 뜻합니다.
선형 구조의 종류는 다음과 같습니다.
순차리스트(배열), 연결리스트(단순연결, 이중연결, 원형연결), 스택, 큐, 데크
순차리스트(선형리스트) == 배열
순차리스트는 배열과 동일한 구조입니다. 특징으로는 물리적인 구조와 논리적인 구조가 동일하고 자료들간 연속적인 순서를 가지고 있습니다. 때문에 데이터 접근엔 용이하지만 데이터를 중간에 삽입한다면 데이터 사이에 공간을 만들기 위해 데이터를 한칸씩 미루어야 하는 단점이 존재합니다.
만약 A[6] 배열에서 인덱스2번 자리에 데이터를 넣으려면 [마지막인덱스(5) - 삽입할 인덱스(2)+1 = 4]
데이터가 총4번 움직여야 합니다. (요약 : 인덱스 뒤에 데이터가 몇개 남았는가 == 움직인 횟수)
인덱스 2번을 삭제한다면 마지막인덱스(5)-(삭제할 인덱스(2) +1)+1 = 4
데이터는 총 3번 움직입니다.
순차리스트 용도 :
같은 형태의 자료형을 대량으로 저장해야 할 때(int형이면 int형만, String형이면 String끼리만 저장 가능)
하나의 변수처럼 사용할 수 있어서 매우 편리하다.
2차원배열의 물리적 저장방법
2차원 배열은 행우선 방법, 열우선 방법이 있다.
실제 메모리에 저장되는 구조는 1차원이다 보니 저장방법을 두가지로 나눌 수 있다.
행우선 방식의 경우 1차원 배열과 동일한 구조이다 우측의 인덱스를 따라 메모리에 저장된다.
열 우선방식의 경우 데이터를 세로(열)순서대로 저장하는 방식이다.
3차원 배열은 면이 가장 먼저 우선순위를 갖는다
-다항식을 배열로 표현하기
이때 차수와 항의 개수 차이가 심한 희소 다항식은 메모리가 낭비된다
f(x)=3x100제곱+3 은 항의 개수가 적은 희소 다항식이다 배열은 1001개가 생성되지만 실제 데이터는 2개만 들어있다.
따라서 다음 2차원 배열을 이용해서 효율적으로 표현할 수 있다.
-행렬의 표현
희소 다항식과 마찬가지로 희소 행렬의 경우 2차원배열로 요약할 수 있다
연결리스트
기존 순차리스트 데이터 삽입, 삭제가 발생할 경우 데이터를 물리적으로 연속시켜야 하기 때문에 원소들을 이동시키는 추가 작업이 필요했습니다.
단점 보완을 위해 포인터 개념이 추가되었습니다. 자료들이 메모리에 연속적으로 저장되지 않고 포인터를 이용해 다음 데이터를 가리켜 순서를 구성합니다.
연결리스트에서는 원소 하나를 '노드'라고 표현합니다. 노드는 실제 값을 저장하는 데이터필드, 다음 노드를 가리키는 링크필드로 구성되어 있습니다. 링크필드는 포인터 변수를 이용해 주소를 저장합니다.
리스트 week가 있다면 week는 첫번째 노드 '월요일' 을 가리키면서 리스트 전체를 의미하기도 합니다.
'월요일'은 link를 통해 '화요일'을 가리킵니다 마지막 노드인 '일요일'의 link는 NULL이 저장되어 있습니다.
◎단순연결리스트
하나의 link로 다음 노드와 연결된 구조입니다. 구조가 단순하고 역으로 읽을 수 없는 단점이 존재합니다.
또한 어느 링크 하나가 값을 잃어버리게 되면 후속 노드는 모두 잃게되는 위험성이 있습니다
0 첫번째 노드로 삽입하기
1. getNode()로 새로운 노드 할당받아 new생성
2. new.data data필드에 데이터 저장
3. new.link link필드에 다음 노드 가리키기
4. L이 새로운 노드를 가리키도록 저장
-중간 노드로 삽입하기
1. 데이터 생성, 입력
2. new가 b를 가리킬 수 있도록 link에 저장
3. a가 new를 가리킬 수 있도록 link 수정
-마지막 노드로 삽입
1.데이터 생성, 입력
2. while(temp.link가 NULL 인지) //마지막 노드를 찾기 위해
temp엔 tmep.link를 저장 //계속 다음 노드로 옮겨감
3. 마지막 노드를 찾으면 temp.link에 new를 저장
4. new.link에 NULL //마지막임을 표시
-노드삭제 a -> b -> c
1. new가 B의 정보를 가짐
2. A.link에 new.link 저장
3. returnNode(new)로 메모리해제
◎원형 연결 리스트
마지막 노드는 NULL이 아닌 첫번째 노드 주소 무한루프를 돌 수 있으므로 Head포인터를 이용해 루프를 빠져나와야 한다.
-첫 노드로 삽입
1. 데이터생성, 입력
2. temp가 마지막 노드 찾기( while temp가 L가 아닌동안)
3. new.link에 temp.link //기존 첫번째 노드를 가리키기 때문
4. temp.link에 new //마지막 노드는 new를 가리키게 됨
5. L에 new를 저장 //온전한 리스트 되었음 L은 리스트포인터
0마지막 노드 삽입
단순연결리스트 마지막에서 new는 NULL이 아닌 첫 노드를 가리키기만 하면 된다
◎이중 연결 리스트
한 방향이 아닌 이전 이후 노드의 주소를 모두 저장한 형태, 메모리공간이 더 필요하다
순방향, 역방향이 이동이 가능하며 링크(포인터)를 잃어버려도 복구가 가능하지만 그만큼 구조가 복잡해 졌습니다.
◎이중 원형 연결 리스트
무한루프에 빠질 가능성이 있고 HEAD포인터로 빠져나와야 한다03. 구조에 따른 분류
댓글