[Data Structure & Algorithm] 포인터 & 연결 리스트

안녕하세요~ 저는 부산멤버십 21-1th 김재진이라고 합니다.

이번 주제는 배열과 포인터(Array & Pointer)입니다. ^^ 다들 아시겠지만 배열과 포인터는 프로그래밍에서 없어서는 안될 요소들이죠.

그러면 시작해볼까요?

이글의 목차

• What is Pointer?
• Pointer by Data Type
• Multi Pointer
• What is Array?
• One dimensional Array
• Multi dimensional Array

What is pointer?

포인터란 무엇일까요? 포인터는 아래와 같은 특징을 가지는 변수입니다.

 변수의 주소값을 가지는 변수
 운영체제의 비트수의 따라서 포인터의 크기도 달라진다.
가리키는 변수의 데이터타입과 포인터변수의 데이터타입이 같아야 한다.

이렇게 텍스트로는 이해가 안될겁니다.
가시화를 해서 볼까요?

이제 이해가 가시나요? 포인터는 일반 변수를 가리킵니다. 일반 변수 a의 주소값을 포인터 p가 담고 있습니다. 가리킨다고 하면 이해가 좀 안될것인데, 가리킨다긴 보다는 일반 변수의 주소값을 가지고 있습니다.

그래서 가지고 있는 일반 변수의 주소값을 가지고 변수의 값을 조작할 수 있습니다. 뒤쪽에 가서 예쩨를 통해서 포인터로 할 수 있는 일을 설명하도록 하겟습니다.

Pointer by data type

포인터의 데이터타입은 담을 변수의 데이터타입과 같아야한다?

왜 같아야할까요? 변수가 할당될 떄는 그 변수의 저장공간이 필요합니다. 메모리의 변수가 할당될 떄 변수의 데이터타입의 따라 차지하는 공간이 달라질 수 있기 때문에 데이터타입은 중요합니다.

그러면 변수의 주소값을 가지는 포인터는 왜 자신이 담을 변수와 데잍타입이 같아야할까요? 그 이유는 담아야할 변수의 주소값이 메모리 공간에 차지하는 위치기 때문에 그만큼의 주소를 허용할려면 같은 크기의 포인터타입이 되어야 가능하기 떄문입니다.

그러면 데이터타입의 의한 포인터에 대해서 예제로 살펴보겠습니다.

구조체 포인터 예제

포인터는 구조체타입의 포인터도 가능합

 

니다. ㅗ스코드를 보시다시피 구조체의 주소값을 참조하여 간접적으로 구조체의 멤버변수를 조작하는 것을 볼 수 있습니다. 실제로 코드를 돌려보시면 더 자세히 알 수 있을 것입니다.

함수 포인터 예제

함수의 이름은 그 함수의 시작 주소값입니다 그래서 함수포인터를 만들어서 함수의 이름을 참조하여
간접적으로 호출할 수 있습니다. 참 신기합니다

다음은 포인터를 주로 쓰는 기법인 Call by reference입니다.

왼쪽에 코드는 Call by value이고, 오른쪽의 코드는 Call by reference이비다. 두가지 소스의 차이는 무엇일까요? 하나는 값을 복사하는 것이고, 하나는 변수의 값을 복사하지 않고 변수의 주소를 넘겨주고,

그 주소값을 참조하여 변수의 값을 조작하는 것입니다. 이렇게 하면 변수의 주소값만으로 큰 용량의 데이터타입을 참조하여 메모리 낭비없이 이용할 수 있습니다. 좋은 기법입니다. 주로 C언어에서는 이렇게 큰 데이터(구조체)의 첫번째 주소값만 넘겨줘서 메모리 낭비를 줄입니다.

다음은 대망의 멀티 포인터입니다! 멀티 포인터?? 포인터는 일반 변수의 주소값을 담는다고 했습니다. 그렇다면 일반 변수가 아닌 포인터 변수의 주소값을 가지는 변수는 어떻게 해야할까요? 잘 생각해보면 포인터변수도 주소값을 가지고 있습니다. 그렇다면 포인터변수도 포인터변수로 인해서 담을 수 있겠죠?

바로 그것입니다.

먼저 예제를 보여드리자면

swap을 잘 보시면 더블 포인터를 사용했습니다. 더블포인터는 포인터의 별이 2개 달린것이 더블 포인터이고, 3개 달리면 삼중포인터입니다. 2개가 달려 있다는 것은 일중포인터를 담을 수 있따는 것입니다.

더블 포인터에서 일중포인터의 주소값을 참조하여 단일 포인터가 가르키는 변수의 값을 조작할수도 있고
포인터 변수의 주소값을 조작할수도 있습니다. 주로 연결리스트에서 자주 사용합니다.

다음은 배열입니다.

배열의 사전적 의미로는 "동일한 성격의 데이터를 관리하기"라고 되어 있는데, 배열은 데이터타입이 같은 변수들을 여러개 만들기 힘들 때 하나로 묶어서 인덱스로 접근하는 데이터타입입니다.

변수명을 짓기가 제일 힘이 듭니다. 이럴 때 같은 데이터타입의 변수명들이라면 배열로 선언해서 사용하면 아주 편리하게 사용할 수 있습니다. 배열도 여러가지가 있는데 행렬처럼 행과 열이 있다고 생각하시면 됩니다.

최대값 구하는 1차원 배열 예제

1차원 배열은 코드로 보면 int a[] = { 1,2,3,4,5,6,7,8,9,10 }; 이런식으로 메모리에 할당될 때부터 초기값을 지정하는 방법이 있고, 나중에 지정하는 방법이 있습니다.

정수의 최대값을 구하는 함수를 만들기 위해서는 정수의 변수가 필요하고, 이런 정수타입의 변수들이 나열되어 있다가 최대값 함수를 사용하면 자동으로 최대값을 뽑아낼 수 있습니다.
이런식으로 같은 데이터타입인데 여러개의 변수를 지정하려고 할 떄, 하나로 묶어서 사용할 떄 쓰입니다.

2차원 배열
 

int array[3][3] = { { 1,2,3 },

                              { 4,5,6 },

                              { 7,8,9 } };

2차원 배열은 1차원 배열이 열로만 이루어져있다고 생각하면 2차원배열은 1차원 배열의 연장선이라고 보시면 됩니다. 행이 추가되었죠.

역행렬 구하기 2차원 배열 예제

잘 보시면 2차원배열은 행렬하고 비슷하게 생겼죠?
그렇다면 2x2 역행렬을 배열로도 구현이 가능하다는 것을 생각할 수 있을 겁니다.

또한 2차원, 3차원, 4차원... 등 배열의 종류는 더 많이 존재하지만 주로 3차원까지만 사용합니다. 4차원 이상가면 우리가 개발하기에 어렵게 생각을 해야되기 떄문입니다.

이상으로 배열과 포인터는 마치도록 하겠습니다. 배열과 포인터는 제일 기본이면서도 어려운 데이터타입입니다. 하지만 중요하기 때문에 꼭 숙지하셔야 됩니다.

다음에는 더 자세한 내용으로 포스팅하겠습니다. 그럼 이만~

안녕 




안녕 하십니까 ~ ! 저는 부산 멤버십 21-1th 허단 이라고 합니다~!
제가 포스팅이라니 긴장도 되고 설레기도 하는데요~ 모두 알고 있더라도 한번더 짚어 가자는 의미로 자료 구조 연결 리스트에 대해 쓰도록 하겠습니다. 미숙 하더라도 잘 봐 주세요~!

목차

리스트란?
리스트 특성과 종류
단순 연결 리스트
단순 연결 리스트 구현 
환형 연결 리스트


리스트란?

우리들이 자료를 정리하는 방법 중의 하나인데 밑의 그림과 같이 일상 생활에서 많은 리스트를 사용하고 있는데 오늘 해야 할 일이나 슈퍼에서 사야할 물건들을 리스트로 정리합니다. 리스트에는 보통 항목들이 차례대로 정리되어 있습니다. 리스트의 항목들은 순서 또는 위치를 가집니다.
       

  

리스트는 집합하고는 다른데 집합은 각 항목간에 순서의 개념이 없습니다. 모두들 많이 사용하는 핸드폰의 수신문자 메시지의 수신 리스트도 하나의 리스트라 할수 있습니다. 이들 리스트를 가지고 다음과 같은 연산들을 생각할수 있습니다.

l새로운 항목을 리스트의 끝,처음,중간에 추가한다.

l기존의 항목을 리스트의 임의의 위치에서 삭제한다.

l모든 항목을 삭제한다.

l기존의 항목을 대치한다.

l리스트가 특정한 항목을 가지고 있는지를 살핀다.

l리스트의 특정위치의 항목을 반환한다.

l리스트안의항목의 개수를 센다.

l리스트가 비었는지,꽉 찼는지를 체크한다.

l리스트안의모든 항목을 표시한다.
 

리스트 특성 과 종류

연결 리스트의 장점으로 정적인 배열과는 달리 동적으로 리스트를 구성할수가 있습니다. 즉 필요하면 할당을 하고 필요가 없으면 없앨수가 있겠습니다.

그리고 동적으로 수시로 할당 해제 되므로 메모리의 연속된 공간을 차지하지 못합니다.
배열 같은 경우는 크기가 정해져 있어서 임의로 크기를 늘이거나 줄일수 없지만 리스트를 구현 하면 이러한 불편은 사라지게 됩니다.

그리고 이러한 특성으로 인해 메모리를 절약할수 있는 이점이 있습니다 하지만 리스트를 구현 시에 복잡도가 배열에 비해 복잡하기 때문에 코드 작성시 구현이 어렵고 오류가 발생하기가 쉽습니다.

연결 리스트의 종류에는 

 각 node 별개수와 링크 연결 상태에 따라서

1.단순 연결리스트

2.환형 연결리스트

3.이중 연결리스트

4.이중 환영연결 리스트
 

으로 구성 되어 집니다. 이 포스팅에서는 1번과 2번까지만 다루도록 하겠습니다.



단순 연결 리스트

연결 리스트는 Node 와 Link 로 구성 되어져 있는데 여기에 헤드 포인터라는 리스트의 첫번째를 가리키는 변수도 존재합니다.
 
l Node= 데이터필드 + 링크필드
 

<!--[endif]-->

l 헤드포인터(head pointer): 리스트의 첫 번째 노드를 가리키는 변수
 

노드는 리스트의 기본 단위로 안에는 data 와 link 로 구성 되어져 있습니다. 그리고 생성시에 필요할 때마다 동적 메모리 생성을 이용하여 노드를 생성합니다. 그래서 필요할때마다 저장하고 없앨수 있어 메모리 절약에 용이합니다.

단순 연결 리스트의 특성으로 여러 가지가 있겠지만 그중에서 밑의 3가지가 있을수 있습니다.

l 하나의링크 필드를 이용하여 연결

<!--[endif]-->

l 마지막Node의 링크 값은 NULL 을넣을수도있고 자기 자신을 가리킬 수도 있다. 

<!--[endif]-->

l 링크필드는 뒤의 node 만을 알수 있지 앞의 Node가 무엇인지를 알수 없다

단순 연결 리스트 구현

연결 리스트에서 노드의 C언어의 구조체를 이용하여 정의됩니다. 구조체 안에서는 데이터 를 저장하는 데이터 필드와 포인터가 저장되어 있는 링크 필드가 존재합니다. 데이터 필드에는 현재 정의되고 있는 구조체를 가리키는 포인터가 정의됩니다.

typedef int element;

typedef struct ListNode
{

  elementdata;

  struct ListNode *link;  

} ListNode;

노드의 구조가 구조체를 이용하여 정의되었지만 아직 노드는 생성되지 않았음에 주의하여야 합니다. 위의 구조체는 일반적으로 사용되어지는 노드의 구조체 입니다.

일반 적으로 연결 리스트에는 필요할 때마다 동적 메모리 할당을 이용하여 노드를 동적으로 생성합니다. 다음의 코드에서는 임시 포인터 변수 p1 을 만들고 malloc 함수를 이용하여 노드의 크기만큼의 동적 메모리를 할당 받는데. 이 동적 메모리가 노드가 되는 것입니다.

ListNode *p1;

p1 =(ListNode *)malloc(sizeof(ListNode)); 
 

위의 코드까지 실행이 되었으면 하나의 노드가 생성이 된것입니다. 하지만 노드만 생성이 되었지 아직 아무것도 채워 지지는 않았습니다. 뭔가 아쉽네요 

다음 절차는 새로 만들어진 노드에 데이터를 저장하고 링크 필드를 NULL 로 설정하는 것입니다. 또한 헤드 포인터가 새로 만들어진 노드를 가리키도록 값을 변경하는 것입니다. 여기까지 진행되면 드디어 노드안에 값이 들어가고 link 필드의 초기화가 이루어 집니다.

                       p1->data = 10;

                                          p1->link = NULL; 

이제 노드들끼리 연결을 시켜 보겠습니다. 일반적으로 연결 리스트에는 여러개의 노드가 서로 연결되어 있습니다. 따라서 똑같은 방식으로 두 번째 노드도 역시 동적으로 생성하고 첫 번째 노드의 링크 필드가 두 번째 노드를 가리키도록 하여 두개의 노드를 서로 연결 시켜 보도록 하겠습니다.

ListNode *p2;

p2 =(ListNode *)malloc(sizeof(ListNode));

p2->data = 20;

p2->link = NULL;

p1->link = p2;

P2->link = p2;

이와 같이 하였으면 최종 적으로 두개의 노드는 서로 연결이 되어 있을 것입니다.

노드를 더 생성하고 싶으면 지금까지의 과정을 원하는 만큼 반복을 하면 됩니다. 즉 함수로 하나 만들어서 언제든지 끌어다 쓰는 식입니다.

한가지 주의할 점은 동적 메모리 할당을 이용항였기 때문에 사용이 끝나면 반드시 메모리를 해제해 주어야 합니다 즉 사용이 끝나게 되면 다음의 과정을 수행 하여야 합니다. 간단 하지만 까먹지 않도록 주의 하도록 합시다.

                                     free(p1);
                                     free(p2);

이때 까지의 수행을 완벽히 해내었으면 노드를 성공 적으로 생성 하게 되었습니다.~~! 하다 보니까 어렵지 않게 수행 하게 되었습니다.

지금까지 노드 생성까지 하였는데 이것 만으로는 완벽 하다고 할수 없을 것이다. 생성 하면 이용 해 먹어야 하는데 지금은 다른것을 할수가 없습니다. 가령 삽입, 삭제, display, 검색, 역순 으로 출력 하기 등등 많을 것인데 이 뒤에는 삽입 까지만 하도록 하겠습니다. 나머지는 자력으로 한번 연습해 봅시다~!

자 그럼 이제 생성 한 노드로 언제든지 늘려서 사용할수 있지만 만약 노드를 중간에 삽입 하고자 한다면 어떻게 하여야 할까요? 앞에서는 단순히 노드 뒤에 노드가 붙는 식인데 중간에 삽입 하려면 여러 가지 작업을 하여야 할것입니다. 중간에 삽입 하려면 다음과 같이 3가지의 예외가 있을수 있습니다.

(1)head가 NULL인 경우: head가 NULL이라면현재 삽입하려는     Node가첫 번째 Node가된다. 따라서head의값만 변경하면 된다.
 

(2)(2) p가 NULL인 경우 : 새로운 노드를 리스트의 맨앞에 삽입한                         다.

다. 

(3)head와 p가 NULL이아닌 경우: 가장일반적인 경우이다.         new_node의 link에 p->link값을복사한 다음, 

      p->link가 new_node를가리키도록 한다. 

위에 나와 있는 (1),(2),(3) 번으로 알고리즘을 구성 해보자 먼저 하나의 함수를 만들어서 ListNode 의 헤더의

이중 포인터를 넘겨 주고 새로운 노드와 현재 노드의 포인터 값을 넘겨 주자. 

처음 에는 공백 리스트인 경우의 예외일 경우 그다음은 p가 NULL 이면 첫번쨰 노드로 삽입 마지막으로 이도

저도 아니면 (3) p 다음에 삽입이다 이 삽입은 처음 노드 생성 과 다르게 중간에 삽입 할수가 있다. 

main 에서 실행 해보면 다음과 같은 결과가 나온다.

 

            

           자 이상으로 삽입 까지 하였습니다. 나머지는 한번 연습 해보도록 합시다~!




환형 연결 리스트


원형 연결 리스트는 리스트의 마지막 노드의 링크가 첫번째 노드를 가리키는 리스트 입니다. 다시 예기 하면 노드의 링크 필드가 NULL 이 아닌 첫번째 노드 주소가 되는 리스트 입니다.

환형 연결 리스트의 특성으로

l 마지막 노드의 링크가 첫번째 노드를 가리키는 리스트

l 한 노드에서 다른 모든 노드로의 접근이 가능

 
l 보통 헤드포인터가 마지막 노드를 가리키게끔 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비하여 용이



 환형 연결 리스트의 삽입 에는 2가지 예외가 있습니다. 그 첫번쨰 

 

 

 
그 두번째로

 

                

자 환형 연결 리스트 삽입 까지 끝났습니다.~!!

모두들 수고 하셨습니다.~! 포스팅 끝까지 봐주신거 감사합니다 ~

모자란 실력으로 포스팅 하려니 힘드네요 ^^; 모두들 하는일 잘되시고 다들 즐코딩 하세요~!!

 

 

d