마니의 개발일지

링크드 리스트

링크드 리스트는 대표적으로 두가지 형태가 있다.

1. 단일 연결리스트

단일 연결리스트는 말그대로 리스트의 형태가 단 하나로 연결되어 있는 형태이다.

말로만 하면 어려우니 아래 그림을 보자

이 그림은 단일 연결 리스트의 형태를 나타낸 그림이다(출처: http://blog.naver.com/jak500/220220692977)

노드는 우리말로 마디라는 뜻인데 링크드 리스트는 '노드를 연결해서 만드는 리스트'라고 하여 붙여진 이름이다.

링크드 리스트의 노드는 위 그림처럼 데이터를 저장하는 데이터필드와 다음 노드의 주소를 저장하여 연결고리를 만드는 포인터(Ptr)로 이루어져 있다.

링크드 리스트에는 헤드와 테일이 있다.

헤드는 리스트의 첫번째 노드를 지칭하고 테일은 리스트의 마지막 노드를 의미한다. 알아두면 다음 글부터 이해하기 수월하다.

 이제부터 직접 구현을 해보자.

리스트에는 5가지의 주요 기능있다.

1. 노드생성

2. 노드 연결

3. 노드 탐색

4. 노드 삭제

5. 노드 삽입

링크드 리스트의 노드를 C언어로 표현하면 다음 그림과 같은 구조체로 나타낼 수 있다.

이 코드에서 data 필드의 자료형이 int 지만 조금 단순하게 하기 위한 것이니 나중에 공부를 마치고 다양한 프로그램을 제작할 때에는 그에 맞게 바꾸거나 추가해주면 된다. 또한 struct의 앞에 typedef라는 키워드가 붙은 이유는 기존의 struct ListNode를 사용하기 위해서는 struct ListNode List와 같이 struct 키워드를 동반해야 하는 불편함이 있기에 typedef 키워드를 사용하여 구조체를 정의 하여 사용한 것이다. 이제 ListNode List와 같이 간단하게 만들 수있다.

바로 노드의 생성부분을 설명하기 전에 C언어에 존재하는 저장공간에 대해 간단하게 설명하고 진행 하겠다.

C언어에는 3가지 저장공간이 존재한다.

먼저 전역변수나 정적변수등을 저장하는 정적메모리, 지역 변수가 저장되는 자동메모리, 마지막으로 자유 저장소이다.

정적메모리는 프로그램이 종료될때 데이터가 초기화된다.

자동 메모리는 블럭 단위가 종료될때 데이터가 초기화된다.

{
       int a;
       char b;
       double c;
}

위와 같은 코드에서 블럭이 종료되면 블럭안의 변수에 할당된 데이터의 공간 또한 초기화 된다. 

이 과정은 함수에서도 적용된다.

그렇다면 남은 저장공간은 자유 저장공간이다.

이 저장공간에 노드의 데이터를 저장하기 위해서는 malloc()함수가 필요합니다.

void* malloc(size_t size);

malloc() 함수의  반환형인 void*는 '만능 포인터'이다.

어떤 형이라도 가르킬수 있다.

malloc()함수를 이용하여 메모리를 할당해주는 예제는 아래와 같다.

이제 이렇게 head노드가 완성 되었다.

이제 노드 생성 부분의 코드를 보자

new_Node -> data =data  //인자로 노드에 저장할 data를 받고 노드를 생성한뒤 노드의 data필드에 인자값으로 받아온 data를 저장한다.

new_Node -> next = NULL  //그후 노드의 다음 노드에 대한 포인터는 NULL로 초기화 해준다.

return new_Node;  //새로 생성한 노드의 주소를 반환 한다.

이제 새로운 노드를 생성했다.

그럼 생성한 노드를 이전의 링크드 리스트의 테일노드 뒤에 연결하는 역활을 하는 함수가 필요하다 

방금 만든 add()함수로 새로운 노드를 생성한뒤 새로 생성한 노드의 주소를 테일노듸의 next에 저장해 주면 될것이다.

먼저 헤드노드와 새로 연결해줄 노드의 주소값을 받아온다.

그후 head를 검사하는 이유는 처음 실행했을때 head의 값이 NULL이면 새로 추가하는 노드가 head노드가 되기 때문에 if문으로 처리를 해주었다.

head노드가 존재하면 Tail노드에 head노드의 주소를 저장시킨다.

그럼 Tail노드는 head노드의 정보를 가진 노드가 된다.

그후 while()문으로 Tail노드의 next가 끝에 도달할때 까지 반복해준다.

Tail노드의 next가 NULL이면 Tail노드의 next에 new_Node를 저장해준다.

이렇게 생성한 노드를 링크드 리스트의 테일노드의 next에 연결 해주는 과정까지 끝났다.

이번엔 현재 링크드 리스트에 연결되있는 노드를 모두 탐색하는 함수를 만들어 보자.

코드를 살펴보자.

먼저 Head노드의 주소를 받아왔고 Node라는 새로운 노드를 만들었다.

if()문으로 Head의 주소에 있는 데이터가 NULL값이면 NotData를 출력시키고

NULL이 아니면 Node에 Head의 주소를 저장한다.

위에서 테일의 마지막을 찾는 방법과 동일하다. 

즉 우리는 이미 링크드리스트의 노드들을 head노드부터 tail노드까지 탐색하는 방법을 이미 적용 시킨것이다.

탐색하는 방법을 그림으로 나타내보자.

실행 시키면 위 그림과 같은 순서로 링크드 리스트의 노드탐색이 진행된다.

자 이제 이러한 탐색 방법을 이용해 일정한 노드의 위치를 찾거나 원하는 노드를 삭제 할 수 있다!

우선 코드를 보기 전에 링크드 리스트의 노드를 삭제하는 방법에 대해서 알아보자.

노드를 삭제 시키는 것은 간단하다.

바로 free()노드를 사용하는 것이다.

free()함수는 자유저장소 즉 동적메모리를 할당해준 변수의 주소를 정확히 알려주면 그 주소에 할당된 메모리를 삭제한다.

|| void free(void* memblock);

자 그럼 밑에 그림을 보자

위 그림에 있는 설명처럼 이전노드의 next에 삭제한 노드가 가르키던 next의 주소를 저장하면 위와 같은 상태가 된다.

이 상태에서 연결이 끊어진 노드의 메모리를 삭제하게되면 노드는 프로그램 상에서 완전히 사라진다.

그럼 한번 코드로 구현해 보자

head노드의 주소를 Node에 저장하고

deleteNode에는 head노드의 next에 저장되있는 주소를 저장한다.

그후 탐색방법과 같은 방법으로 deleteNode의 data가 삭제하고싶은 data와 일치할때까지 반복해서 다음 주소값을 넣어준다.

deleteNode->data가 삭제할 data와 같으면 Node의 next에 deleteNode의 next의 주소값을 저장한다.

이렇게 삭제 함수도 구현을 끝냈다.

이제 마지막으로 삽입이다.

아래 그림은 삽입을 그림으로 표현 한 것이다.

말이 많아 조금 복잡해 보이지만 읽어보면 생각보다 간단하다.

삽입할 노드의 주소를 이전노드의 next에 저장하고 이전노드에 저장되 있던 next의 주소를 삽입한 노드의 next로 넘겨주면 노드의 삽입이 끝난다.

막상 해석하니 생각보다 간단하지 않은가..?

한번 위의 내용을 가지고 코드로 구현을 해보자

삭제함수와 비슷해보이지만 삭제함수가 이전노드의 next를 다음 노드의 주소값으로 연결을 시켜줬다면

삽입함수는 삽입을 하고자 하는 위치의 이전 노드에 저장된 next의 주소값을 삽입하고자 하는 노드의 next로 넘겨주고

이전노드의 next를 삽입한 노드의 주소로 변경시켜주면 구현이 끝난다.

자 이렇게 링크드 리스트의 중요한 기능들을 구현하고 살펴 보았다.

하지만 이 코드들에는 분명 문제점이 있다.

따로 말하지는 않겠지만 꼭 찾아서 수정하여 오류가 발생하지 않도록 해보길 권장한다

아래는 소스코드의 전체 모습이다.

다음에는 이중연결리스트에 대해서 포스팅 하겠다.

감사합니다.

알고리즘이란 무엇일까?

─────────────────────────────────────

알고리즘이란 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다.

또한 알고리즘은 다음과 같은 조건을 만족해야 한다.

1. 입력 : 외부에서 받는 자료의 개수가 0개 이상 존재해야 한다.

2. 출력 : 외부로 출력하는 결과의 값이 적어도 2개이상 존재해야 한다.

3. 명확성 : 알고리즘의 수행과정이 명확하고 애매 모호하지않은 명령들로 구성되어야 한다. 

4. 유한성 : 명령의 개수가 유한해야하고 유한한 시간내에 종료되어야 한다.

5. 효율성 : 모든 알고리즘의 과정은 실행가능해야 한다.

알고리즘에는 복잡도라는 개념이 있다.

복잡도는 알고리즘에서 그 알고리즘이 어느정도 복잡하고 어느정도의 작업량을 가지는지를 알수 있게 해주는 개념이다.

주로 빅오 표기법으로도 부른다.

빅오 표기법 이란?

─────────────────────────────────────

빅오 표기법 이란 프로그램의 복잡도를 시간적으로 표현하는 방법 중 하나이다.

주로 알고리즘의 시간복잡도를 계산하여 알고리즘의 성능을 표현하는데 사용한다.

빅오 표기법에는 대표적으로

O(1), O(log N), O(n), O(N log N), O(n^2), O(n^3) 등이 있다.

O(1): 상수형 빅-오 표기, 데이터 수에 상관없이 연산의 횟수가 고정 된 형태의 알고리즘

O( log N ): 로그형 빅-오 표기, 데이터 수가 증가율에 비하여 연산횟수의 증가율이 훨씬 적은 형태의 알고리즘

O(n): 선형 빅-오 표기, 데이터 수의 증가에 따라 연산횟수가 비례하여 증가한다.

O( N log N ): 선형 로그형 빅-오 표기법, 데이터 수가 증가하면 증가되는 연산횟수가

로그형으로 표기한 알고리즘 보다 조금 더 증가하는 알고리즘

O(n^2): 데이터수의 제곱에 해당하는 연산횟수를 가진 알고리즘

O(n^3): 데이터수의 세제곱에 해당하는 연산횟수를 가진 알고리즘

O(n!): 팩토리얼형 빅-오 표기법, 데이터의 수가 증가할수록 연산횟수가 매우 커진다.

▲ 빅오 표기법들의 시간복잡도 그래프

(평평한 표기법일수록 효율이 좋다.)

위에서 설명한 빅오 표기법을 시간복잡도 순서로 나열하면 아래와 같다.

(시간복잡도가 적은 순서대로)

O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

우선 기초적인 내용은 이정도로 설명하고 다음 글 부터는 자료구조에 대해서 설명할것이다.

자료구조의 설명은 여기서 한다.

자료구조란 무엇일까?

─────────────────────────────────────

 전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다. 사용자가 신중하게 선택한 자료구조는 알고리즘의 효율을 향상시키는데 큰 역활을 한다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

자료구조의 종류로는 리스트, 스택, 큐, 트리, 정령, 탐색 등등 매우 많은 자료구조가 있다.

앞으로 자료구조의 종류에 대해서 설명하고 직접 구현하는 과정으로 진행할것이다.