연결리스트(순차/연결자료구조)어떻게 이해하죠?[1]

본 포스트는 c언어를 중심으로 작성되었습니다.

 

연결리스트(순차/연결자료구조)어떻게 이해하죠?

자료는 구조화 방법에 따라 리스트, 스택, 큐, 등으로 나뉩니다! 우선 순차자료구조를 먼저 알아보겠습니다. 순차자료구조는 논리적순서나 물리저 순서가 항상 일치합니다. 때문에 우리는 그 중에서 c언어에서의 배열기법으로 구현해야합니다.

 

순차자료구조는 연결자료구조와 어떤점이 다른지 한번 알아보겠습니다.

 

메모리저장방식 : 순차자료구조는 말그대로 메모리 시작지점부터 순차적으로 연속하여 젖아하는 대신 연결자료구조는 링크와 노드에 의하여 순서를 표현하는 구현방식입니다.

 

연산 : 추가적 연산을 따라도 메모리 상 빈 영역이 존재하지 않게끔 저장하는 것이 순차 자료구조인 반면, 연결 자료구조는 링크 정보만 변경되고 물리적 순서는 변경되지 않았습니다.

 

기법은 위 두가지의 비교특징에 따라 순차는 배열 연결은 링크와 노드가 필요하다는 점에서 눈치를 채셨겠지만, 포인터 변수를 이용한 구현이 필요합니다.

 

 

1. 선형 리스트

 

자료의 특징이나 구조화하는 기본적인 방법은 나열입니다. 나열은 배열!

 

예를 들면,

과일 : 사과, 오렌지, 귤

차 브랜드 : bmw, ford, hyundai 

 

이런식으로 나열할 수 있겠죠? 이러한 목록을 리스트라고 합니다.

 

그런다음 이 테이블을

1	사과
2	오렌지
3	귤
---	---

이러한 방식을 선형리스트 또는 순서리스트라고 아시면 됩니다.

 

그렇다면 표현방식은 어떻게 될까요?

 

리스트 이름 = (value1, value2, ---,value n); <--- 표현형식은 이렇게 되며 표현 예로는 ---> 과일 = (사과, 오렌지, 귤);

 

공백리스트는 값을 아무것도 두지않으면 공백이겠죠

 

 

2. 선형 리스트 구현

 

앞서 말씀드렸듯이 선형리스트는 배열을 통해 구현합니다. 우선 그중에서 1차원부터 -n차원 까지 이어지는 구현을 해보겠습니다.

 

우선 테이블을 하나 만들어 표현해보겠습니다~

 

아래와 같이 테이블을 만들었ㅅ브니다.

그렇다면 각 메모리 주소는 n으로 시작한다 가정한다면,

n + 4바이트 만큼계속해서 주소는 증가할것을 예상할 수 있습니다.

 

fruit

100

200

300

논리적구조에 따라 코드를 작성해보았습니다.

#include <stdio.h>
 
int main(){
    int i , fruit[3] = {100,200,300};
 
    for (i =0; i<3;i++){
        printf("\n memory : %u, fruit[%d] = %d", &fruit[i], i, fruit[i]);
 
 
    }
    return 0;
}

--출력결과--

memory  = 1000(가정) , fruit  = 100

memory = 1004, fruit = 200

memory = 1008, fruit =300

 

위와 같이 출력됩니다. 즉 정수형 크기 만큼 메모리주소가 늘어나는것을 확인할 수 있었습니다.

 

2-1. 2차원배열 선형리스트

 

바로 예시 테이블을 만들어보겠습니다.

연도와 나이에 따른 사치품 소비량을 예시로 작성하겠습니다

연도\나이	10대	20대	30대	40대
2019	5	30	40	25
2020	8	32	50	10

완성!

 

2차원 배열구조는 논리적으론 행열  구조로 표현합니다. 하지만 실제 메모리상은 그렇게 저장될 수 가 없죠. 물론 1차원 배열로 저장됩니다.

저장될 시 행우선, 열우선 으로 나뉩니다. 

 

말그대로 행 중심으로 한다면 2행 4열 이기 때문에 2 행이 앞서서 [0] [0] ---[1] [3]까지의 순서로 물리적 저장이 이뤄지는 반면, 열 중심이라면 그반대로 저장됩니다. c프로그래밍은 행우선 방법을 사용하여 메모리에 저장됩니다.

 

그렇다면 위 테이블을 토대로 코드를 작성해보겠습니다.

 

#include <stdio.h>
 
int main (){
    int i, n = 0, *point;
 
    int buy[2][4] = {{5,30,40,25},
    {8,32,50,10}};
 
    point = &buy[0][0];
 
    for(i = 0; i<8; i++)
    {
        printf("\n memory : %u, buy[%d] = %d", point,i,*point);
        point++;
    }
    return 0;
}

 

출력결과는 예상하듯 

 

-->memory : 1004(ex) buy1 = 5

 

이러한 방식으로 8번 출력되겠죠? 행의 순서대로 출력됨을 알 수 있습니다.

 

2-2. 3차원 배열 표현

 

필자가 생각하는 복잡한 배열의 표현은 3차원 배열이 아닐까 싶지만, 필자의 실력이 모자랄 수 있다고 생각되는 바이기에 징징대진않겠습니다 ..ㅋㅋ

 

우선 3차원 배열을 또 표현하기 위해서 테이블을 하나 만들겠습니다.

 

브랜드	연도\나이	20대	30대	40대
a사	2019년	57	46	21
	2020년	68	42	19
s사	2019년	43	54	79
	2020년	32	58	81

 

연도와 나이에 따른 선호도 비교를 해보겠습니다.

 

표현을 하려면 어떻게 해야할까요? 앞서 포스팅 했듯이 3차원 배열은 면/ 행/ 열 로 나뉘어 표현됩니다.

 

int like[2][2][3] = {{{57,46,21},{68,42,19}}, {{43,54,79},{32,58,81}}}; <--- 로 표현할수 있습니다

또한, 3차원 배열도 2차원 배열과 마찬가지로 행중심 열중심의 표현이 가능하며 c컴파일러에서의 기본은 행중심입니다.

 

#include <stdio.h>
 
int main (){
    int i, n = 0, *point;
 
    int like[2][2][4] = {{{57,46,21},
    {68,42,19}}, 
    {{43,54,79},
    {32,58,81}}}; 
 
    point = &like[0][0][0];
 
    for(i = 0; i<16; i++)
    {
        printf("\n memory : %u, like[%2d] = %3d", point,i,*point);
        point++;
    }
    return 0;
}

--출력결과--

memory : 1004(ex) like0 = 57 <-- 라고 출력됩니다.

 

또한 본 코드에서는 [2][2][4]로 크기를 설정하고 열에는 3개의 값을 넣었으니, 4번째 값[인덱스상 3]의 자리에는 null이 출력됩니다.

 

욕심 같아선 연결리스트 또한 같이 포스팅해서 같이 알면좋지만 , 너무 내용이 많고 또한 연결리스트는 이해를 정말 잘해야하기때문에 다음포스트로 넘어가 포스팅하도록 하겠습니다.

 

읽어주셔서 감사하며, 댓글 피드백 환영합니다!!