대엉코딩

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를 통한 접근이 간편하며, 이는 큰 장점이다

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

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

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

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

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

* 스택이란 ?

- LIFO(Last In First Out)

- 떠올리기 쉬운것은 주방에 쌓여있는 식기를 놓으면 좋다. 

- 설거지를 해서 위에 쌓으면 사용을 할 때는 위에서 부터 하나씩 가지고 간다.

* 스택의 연산

- 삽입, 삭제, 비어있는지 확인, 상단 확인, 크기 등의 연산이 있다.

- 객체 : 후입선출(LIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : push(x)

               pop()

               size()              

               peek() -> 스택 상단에 위치한 요소를 반환(봄) (스택이 비어있지 않으면)

    시간복잡도 : size()를 제외하고는 모드 O(1)이라고 할수 있습니다.

                            size()는 어떻게 구현하느냐에 따라 다를 수 있습니다.( 배열이나 연결리스트)

- 말이 나와서 하는 것이지만 추상자료형 (Abstract Data Type)은 사실 어떻게 구현하느냐는 사용자는 알 수 없습니다.

   제가 배웠던 것을 항상 떠올릴 때는 문 밖에서 어떠한 입력을 넣고 요구를 하면 안에서는 어떤식이던지 구현을 하여

   정확한 결과만을 문 밖으로 다시 보내주는 것 입니다. 사용자는 결과를 받지만 내부에 어떤식으로 이를 처리 하였는지는

   알 수 없지요

* 스택 활용의 예

- 문서나 그림, 수식 등의 편집기에서 되돌리기 기능

   (최근 사용했던것 부터 다시 되돌리기를 합니다. -스택을 사용하면 편하겠죠????)

- 함수 호출에서 복귀주소 를 기억 할 때

   (예를 들면, main 함수에서 작업을 수행하다가 다른 함수를 호출해서 그 함수로 이동한다고 하면

     그 함수가 끝나고 났을 때 다시 main 함수로 돌아와서 그 다음 작업을 진행 하여야 합니다.

     그럼 그때 복귀주소를 스택에 넣어 놓습니다.)

- main에서 function A를 호출하고 function A에서 function B 를 호출 한다고 가정을 한다면????

    (스택에 우선 main으로 돌아오기 위한 복귀 주소가 먼저  push될 것입니다. 그다음 function A로 가고

      function B가 수행될 때 function A로 돌아오기 위한 복귀 주소가 그 위에 삽입 될 것 입니다.

      function B가 끝나면 스택에서 맨위 (TOP)을 pop해서 function A 나머지를 수행하고 다시 POP 을

      하면 main함수로 돌아올 수 있습니다.)

* 스택의 구현

 - 1. 배열을 이용

 - 2. 연결리스트를 이용

   직접 구현은 하지 않았지만 연결리스트를 사용하면 처음에 스택 사이즈를 지정 해 줄 필요도 없을 것입니다.

     배열을 이용해서 연결리스트 처럼 구현을 하려면 사이즈를 넘어 갈경우 max사이즈를 두배로 증가시켜서

     다시 배열을 만들고 모든 요소들을 새로운 배열로 이동시키고 원래 배열을  delete 시키고 하는 그런 복잡한

     작업을 해야할 것 입니다.