대엉코딩

1. 배열

- 연속된 메모리 상에 위치 (배정) 된다.

- "시작주소 + (자료형의 크기) * INDEX " 를 통해서 접근이 가능하므로 배열의 이름과 INDEX만으로 쉽게 접근

    이 가능하다. (매우 큰 장점)

- 크기와 자료형을 지정해주어야 한다.

- 동적배열로 어느정도 해결이 가능하지만, 배열이 최대크기를 넘어설 때는 Array Doubling이 발생하는데 

- 두배 크기의 배열이 선언되고, 기존의 데이터들을 새로운 두배크기의 배열로 모두 옮겨야 하므로 O(n) 시간이 소요. 

-(여담으로 수업을 들을 당시에 그럼 n크기의 배열에서 계속 삽입,삭제,삽입,삭제가 일어나면 계속 새로운배열이 생기고

  시간이 오래걸리는 것 인가? 라는 질문이 있었는데, 데이터의 개수가 n+1이 되어서 2n짜리 배열을 선언해서 옮겼을 

  때, 삭제연산이 일어나서 다시 n이 되었을 때 바로 다시 크기가 n인 배열로 옮기진 않는다고 한다. 보통은 n/2 정도가 

  되었을 때 옮긴다고 한다.)

- 탐색, 삽입, 삭제

   (1) 탐색

     -> 원하는 위치가 존재할 경우 index로 바로 접근이 가능하다 (O(n))

     -> 특정한 value를 찾고 싶을 때는 앞쪽부터 탐색하므로 O(n)

    (2) 삽입

      -> 특정위치에 삽입한다면 그 위치부터 끝쪽 까지 위치하던 데이터 들을 모두 한칸씩 미뤄야 하므로 (O(n))

      -> 맨 뒤에 삽입일 경우 옮길 것이 없으므로 빠르지만, 최악의 경우는 맨 앞쪽에 삽입할 경우 이므로 n-1개를

          옮겨야 할 수도 있다.

    (3) 삭제

       -> 삭제된 위치로 부터 뒤에 있는 데이터들을 모두 앞쪽으로 한칸씩 당겨주어야한다. (삽입과 같은 맥락)

- 배열은 메모리상에 연속되게 위치하기 때문에 크기가 큰 배열을 선언하려고 할 경우 남은 공간의 합은 충분하더라도

- 연속된 공간이 확보되지 않을 경우 메모리 할당을 못 받을수도 있다.

2. 연결리스트( 링크드 리스트)

- 단순 연결 리스트 (simple linked list)와 이중 링크드 리스트(doubly linked list)가 존재

- (단순 연결 리스트)  - HEAD Pointer를 통해서 접근

- (이중 연결 리스트)  - HEAD,TAIL을 통해서 접근

- 위의 그림과 같이 연결리스트는 연속된 메모리 공간에서 존재하지 않고 다음 테이터를 가리키는 포인터를

- 통해서 다음 원소에 접근한다.

- 연속된 공간이 필요하지 않고, 크기를 미리 지정해줄 필요도 없다.

- 반면, 다음원소를 가리키는 포인터에 대한 공간낭비 (오버헤드)가 발생한다.

- 심한경우를 예로 들자면 char형을 저장하려고 하는 경우 실제 데이터는 1byte인데

- 이중 연결리스트로 구현할 경우 prev와 next에 해당하는 포인터들이 각각 4byte씩 이므로 총 9 byte를 차지 하게 된다.

   (하나의 노드 당) -- 이는 배보다 배꼽이 더 큰 격이다.

- 탐색, 삽입, 삭제

  (1) 탐색

    - 포인터를 따라서 찾아가야 하므로 탐색시간이 오래 걸린다. (O(N)

  (2) 삽입

     - 간단하다. 탐색이 끝난 상태(탐색은 오래걸림)라면 넣고자 하는 위치의 이전 노드의 next 포인터가 해당데이터를            가리키도록 수정하 고, 해당 데이터의 next 포인터가 원래 이전노드가 가리키던 다음 노드를 가리키도록 설정만             해주면 된다.

        (싱글 링크드 리스트일 경우. 이중을 경우 prev,와 next에 해당되는 포인터 모두를 수정)

     - 단순 연결리스트의 경우 head를 통해서만 접근하므로 앞 쪽에 데이터(노드)를 추가하는 것은 빠르다.

     - 이중 연결리스트의 경우 tail을 통해서도 접근이 가능하므로 앞,뒤쪽에 데이터(노드)를 추가하는 것은 빠르다.

  (3) 삭제

     - 삭제 역시 삽입과 마찬가지로 간단하다.

     - 이전 의 노드의 next 포인터를 다음 노드를 가리키도록 수정해 주면 된다.

        (싱글 링크드 리스트일 경우. 이중을 경우 prev,와 next에 해당되는 포인터 모두를 수정)

3. 배열과 연결리스트의 간단정리.

- 배열을 사용할 경우 index를 통한 접근이 간편하며, 이는 큰 장점이다

   저장할 데이터 수가 어느정도 정해져있고, 데이터들을 중간에 삽입,삭제가 많지 않을 떄 좋다.

  연속된 메모리 공간을 요구한다.

- 연결리스트를 사용할 경우, 데이터의 개수에 제한이 없고 , 연속된 공간의 메모리를 필요로 하지 않는다.

  데이터의 삽입, 삭제가 빈번하고 상대적으로 어떤 위치의 데이터에 대한 탐색이 적을경우 좋다.

  포인터에 대한 오버헤드가 발생한다.

참조 타입 변수(레퍼런스) 는 별명과 같은 느낌이라고 보면 될 것이다.

c++의 포인터 와 레퍼런스의 차이점을 알아보자.

# 포인터는 null을 가리킬 수 있지만 참조 타입 변수는 null을 가리킬 수 없다.

   - 포인터를 초기화 하지 않거나 null을 가리키고 있는 포인터에 접근 했을 때

     발생하는 에러가 참조 타입 변수에서는 나타나지 않는다.

# 참조 타입 변수는 선언과 동시에 초기화 하지않으면 컴파일 오류가 발생한다.

# 포인터는 * , -> 등의 포인터 연산자를 통해서 접근 해야 하지만 참조 타입 변수는

   마치 지역변수 처럼 접근할 수 있다.

# 참조 타입 변수는 초기화 과정에서만 값을 할당 할 수 있고 이후에 다시 할당을

   시도 할 경우 컴파일 에러가 발생한다. 하지만 포인터 변수는 참조 대상을 언제든지 변경할 

   수 있다.