IT's me

[자료구조] 연결 리스트의 이해(1)

연결 리스트는 크게 배열 기반 연결 리스트와

연결 리스트 기반 연결 리스트가 있는데

우리가 흔히 사용하는 연결리스트는 후자이기 때문에

연결 리스트 기반의 연결 리스트에 대해 알아보도록 하겠다.

들어가기에 앞서 배열과의 비교가 우선시 되어야 할 것같다.

배열이라 함은 기본 제공되는 상당히 훌륭한 자료구조이다.

배열의 가장 큰 장점 중 하나는 index를 통한 순차접근이다.

배열의 가장 큰 단점 중 하나는 크기가 결정되어야 한다는 것인데

이는 매우 큰 부담으로 작용한다. 물론 크기를 바꿀 수 있는 방법이 없는 것은

아니지만, 그에 따른 비용이 만만치 않기 때문에 큰 단점이라 할 수 있다.

때문에 배열보다 좀 더 유연하고 순차 접근을 훌륭히

 수행할 수 있는 것이 필요한데 이것이 바로 연결 리스트이다.

malloc를 이용한 동적할당이 기본이 되어야하고,

할당된 메모리를 어떻게 접근하고 관리할 것인가가

연결 리스트를 이해하는 것의 가장 큰 이슈가 될 것이다.

1. 구조체의 이해

2. 동적 할당 (malloc)

3. 어떻게 연결할 것인가?

4. 어떻게 순차 접근할 것인가?

1. 구조체의 이해

힙에 할당되어 저장되는 자료를 우리는 노드(node)라고 부른다.

노드는 C에서 구조체 변수이다. (기본 제공 타입이 아님)

이렇듯 노드에는 데이터를 담을 공간과

다음 노드를 가리킬 구조체 포인터를 가지고 있다.

2. 동적 할당

malloc, free는 C언어 기본서 참고

3. 어떻게 연결할 것인가?

들어가기에 앞서 노드의 연결과 참조를 위한 핵심을 훑어보자.

next는 현재 노드의 다음 노드를 가리키고 있다.

이렇게 노드들을 쭉 연결 한다면 비엔나 소시지처럼

연결된 모양이 될 것이고, 결과적으로는 첫 노드의

주소값만 알고 있다면 모든 노드를 탐색할 수 있다.

n1,n2는 노드이고 각각의 데이터를 가지고 있다.

next라는 구조체 포인터는 자신의 다음 노드를 가리키도록 한다.

( 주의할 점은 꼭 현재 노드의 뒤에만 새로운 노드가 올 수 있는 것은 아니다. )

현재 노드의 앞 뒤 어느 곳에서든 노드가 추가될 수 있어야 한다.

4. 어떻게 순차 접근을 할 것인가?

n1의 next는 자신의 다음 노드를 가리키고 있기 때문에

*를 사용한다면 자신의 다음 노드에 접근할 수 있다.

연결 리스트와 배열과의 차이점 그리고 연결 리스트를

구현하기에 앞서어떠한 핵심을 공략해야하는지에 대해

간단하게 알아보았다. 다음 포스팅부터는 이슈들을 하나하나

 해결해가며 연결 리스트를 구현해 보도록 하겠다.

[C#] string 그리고 가비지 컬렉션

유니티를 통해 3D 게임을 만들 때

최적화 문제로 굉장히 고생했던 적이 있다.

그 때 봤던 최적화 팁에서 string + string 은

가비지를 생성한다해서 StringBuilder의 Append를

이용하여 문자열을 병합하라고 했다. 그런데 도대체 왜?

해답은 바로 문자열은 변경할 수 없는 객체라는 것에 있다. (immutable)

그렇다면 변경할 수 없는 거랑 가비지 컬렉션이랑 무슨 관계가 있는 것일까?

앞서 말했듯 문자열은 한번 생성되면 변경되지 않는다.

하지만 사실 문자열을 사용하면서 변경에 대해 어려움을

느낀 경우는 잘 없을 것이다. 이러한 문자열의 표면적인

변경은 쉽지만 내부적으로는 항상 새로운 문자열이 만들어지게 된다.

string str = "하하하";

str += "쏭";

예상대로 "하하하쏭"이라는 결과가 나온다.

그러나 메모리 측면에서는 처음 생성한 str과

이후 추가 문자가 덧 붙여진 str은 완전 다른 객체이다.

즉, "쏭"이라는 글이 추가될 때 새로운 객체가 메모리에 할당되고

이 것을 str이 다시 참조하도록 되는 것이다. 처음에 만들었던

"하하하"라는 객체는 사라지게 되는 것이다. (가비지)

성능을 위해서라면 String 대신 StringBuilder를 사용하자.

후에 좀 더 자세히 다뤄볼 StringBuilder에 대해 알아보자.

앞에 말했듯이 문자열은 변경될 수 없는 객체이기 때문에

문자열에 대한 어떠한 변경도 항상 새로운 객체를 생성하게 된다.

문자열 변경 작업이 빈번하다던지, 대량으로 문자열을 연결할

경우에는 성능을 반드시 고려해볼 필요가 있다.

왜냐하면 앞서 말했듯 문자열의 변경은 가비지를 유발하기 때문.

이 대안으로 StringBuilder 클래스를 생각해 볼 수 있다.

자 그렇다면 string + string을 어떻게 하면 가비지없이

수행해낼 수 있는지 알아보도록 하자.

System.Text.StringBuilder sb = new System.Text.StringBuilder();

sb.Append("하");

sb.Append("하하");

sb.Append("쏭");

StringBuilder는 String과는 달리 변경 가능한 액체이기 때문에

(mustable) string + string의 가비지 문제를 해결할 수 있다.

추가

MSDN의 성능 고려사항을 짚고 넘어가 보자.

MSDN에 따르면 Concat 및 AppendFormat 메서드는 새 데이터를

기존 String 또는 StringBuilder 개체에 연결한다. String개체 연결

작업에서는 항상 기존 문자열과 새 데이터로 새 개체를 만든다. 

StringBuilder 개체는 연결된 새 데이터를 수용할 버퍼를 유지한다.

새 데이터는 공간이 있을 경우 버퍼 끝에 추가되고, 그렇지 않으면

더 큰 새로운 버퍼가 할당되고, 원래 버퍼의 데이터가 새 버퍼에

복사된 다음, 새 데이터가 새 버퍼에 추가된다.

String 또는 StringBuilder 개체에 대한 연결 작업의 성능은 얼마나

자주 메모리를 할당하는지에 따라 달라진다. StringBuilder 연결

작업에서는 StringBuilder 개체 버퍼가 너무 작아 새 데이터를 넣을 수 없는

경우에만 메모리가 할당되는 반면, String 연결 작업에서는 항상 메모리가 할당된다. 

따라서 고정된 수의 String 개체를 연결하는 연결 작업에는

String 클래스가 더 적합하다. 이 경우 개별 연결 작업이 컴파일러를

통해 단일 작업으로 결합될 수 있다. 임의의 개수의 문자열을 연결하는

(예 : 루푸에서 읨의의 개수의 사용자 입력 문자열을 연결할 경우)

연결 작업에는 StringBuilder 개체가 더 적합하다.

[C#] 이벤트와 델리게이트

어떠한 일이 생겼을 때 이를 알려주는 객체가

필요한 경우가 있다. 예를 들어 사용자가 버튼을

클릭했을 때 이를 알려주는 객체가 그 것이다.

이런 객체를 만들 때 사용하는 것이 바로 이벤트이다.

이벤트의 동작 원리는 델리게이트와 거의 비슷하다.

이벤트는 델리게이트를 event 한정자로 수식해서 만든다.

자 그럼 이벤트는 어떻게 만드는지 차근차근 보도록 하자.

1. 델리게이트 선언. 클래스 밖에 선언해도 되고 안에 해도 된다.

2. 선언한 델리게이트의 인스턴스를 event 한정자로 수식해서 선언

(여기서는 클래스 내부에 있어야 한다.)

3. 이벤트 핸들러를 작성한다. 선언한 델리게이트와 일치하는 메소드여야 한다.

4. 클래스의 인스턴스를 생성하고 이 객체의

이벤트에 3에 작성한 이벤트 핸들러를 등록한다.

5. 이벤트가 발생하면 이벤트 핸들러가 호출된다.

앞서 보았듯이, 이벤트는 델리게이트에 event 키워드로

수식해서 선언한 것에 불과하다. 과연 무엇이 다를까?

이벤트와 델리게이트의 가장 큰 차이점은 바로

외부에서 접근을 할 수 있느냐 없느냐

이벤트는 public 한정자로 선언되어 있어도

자신이 선언되어 있는 클래스 외부에서는

호출이 불가능하다. 반면 델리게이트는

public이나 internal로 수식되어 있으면

클래스 외부에서라도 얼마든지 호출 가능하다.

이벤트의 이러한 특성은 견고한 이벤트 기반

프로그래밍을 가능하게 한다.

때문에 이벤트는 객체의 상태 변화나

사건의 발생을 알리는 용도로 사용이 되고

델리게이트는 콜백용도로 사용이 된다.