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

본 포스트는 C언어를 중심으로 작성되었음을 알려드립니다.

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

앞서서 순차리스트를 알아보았습니다. 만약 못보셨다면 앞서 나가셔서 보시는것을 추천드리며 포스트를 시작하겠습니다.

 

자료구조를 구현하는 방식에는 앞서 말씀드린 논리적/ 물리적 순서가 있다는 것을 알고 있습니다. 순차리스트는 이에대한 논리적 물리적 구조의 순서가 일치해야합니다. 또한 배열내 요소를 삭제 또는 삽입을 하게되면 모든 메모리가 유동적으로 움직여야 합니다. 그렇기 때문에 메모리사용에 있어서 매~우 비효율적이라는 것입니다.

 

그렇다면 연결자료구조는 어떨지 확인해보겠습니다.

우선 앞서 간략히 설명드리자면, 순차 자료구조와 다르게도 논리적/물리적 순서가 동일하지 않아도 아무 상관없습니다. 좀 더 설명드리면, 요소 순서를 표현하는것이 아니라, 각 요소에 저장되있는, 링크에 의해 순서가 연결되기 때문에 순서따윈 의미가 없는것이지요.

 

그럼 연결 자료구조에서의 요소는 다음 요소에 대한 주소를 저장한다고 했습니다. 그렇다면 요소,주소 단위로 저장된다는 것이고, 이를 Node라고 합니다. 노드는 데이터필드와 다음 노드의 주소를 저장하는 링크 필드로 구성됩니다. 논리적 구조를  테이블로 표현해보겠습니다.

 

data	link
value __init__	next value address __init__

위와 같은 방식으로 표현할 수 있습니다.

 

그렇다면 실제 코드상에서 쉽게 표현하겠습니다.

우리는 순차리스트와 연결리스트를 비교해서 표현해보겠습니다.

 

순차리스트의 표현방식 다들 기억하시죠?

 

number

1

2

3

4

5

6

7

 

논리적 구조에 기인하여 만들었습니다. 만약 넘버 순차리스트안에 있는 '4' 라는 값에 엑세스하려면 1,2,3,을 건너 뛰어서 찾아가야하는 비효율적인 구조를 가지고 있습니다,

 

반면에, 연결리스트는

 

number *p	1	link ->	2	link ->	3	link ->	4
link ->	5	link ->	6	link ->	7	link ->	8/ null

 

라고 표현됩니다. 마지막 8 값의 노드의 링크 밸류는 NULL로 저장됩니다. 이유는 전달받을 주소가 없기 때문입니다. 처음 number 변수에는 포인터 변수를 선언하여 사용합니다. 포인터를 담을 메모리공간이 더 필요하지만, 삽입이나 삭제시에  추가 작업없이 삽입삭제연산이 가능합니다.

#include <stdio.h>
 
typedef struct Node{
    int Data[4];
    struct Node* link;
};

리스트 노드의 구조체는 위와 같이 표현합니다.

 

간단하게 생각한다면 

기차놀이를 생각하시면됩니다. 필자는 a,b,c와 함께 기차놀이를 진행합니다. 저는 무조건 a라의 손을 잡아야합니다. a는 c를, c는 b를 잡아야합니다 그렇다면 모두가 연결되는 기차가 완성됨을 알 수 있습니다.

 

필자

링크

a

링크

b

링크

c

링크(null)

 

로 표현됩니다. 

 

이를 컴퓨터 공학적으로 풀어보자면 제 존재는 포인터변수가 되어 기차놀이의 상징이 되며 제 링크는 a의 주소입니다. a,b,c 또한 저와 같은 구조를 지니고 있습니다. 

 

 

오늘 포스트는 간략하게 설명하였습니다. 왜냐하면 원형 연결리스트 다중 연결리스트를 한꺼번에 포스팅 하기에 벅차서 하기 힘듭니다..

 

계속해서 연결리스트에 대한 포스트는 진행하겠습니다! 

 

댓글 피드백 환영합니다 모두!!