06Dec2019 TIL

Today I learned :

• Datastructure - Stack
• Datastructure - Queue
• Datastructure - Linked list

---

전 날 고객사랑 저녁에 술먹은 여파로 피곤해 죽을 뻔 했지만, 조금이라도 공부한 내 자신 칭찬해......ㅎㅎㅎ 
여기 그림들은 픽토그램은 Icon made by turkkub from www.flaticon.com 이며, 
파워 포인트를 이용하여 그림으로 재구성했다! 

 

Stack 과 Queue 는 각종 검색을 통해 즉각적으로 이해할 수 있는 데이터 구조 형식이었다.

---

Stack : 나중에 넣은거 제일 먼저 빼는 것 (= 처음에 넣은거 제일 나중에 빼는 것)

    eg) 비행기 화물 ; 제일 먼저 체크인 해서 짐 맡기면, 나중에 짐 찾을 때 제일 늦게 나온다 (ㅋㅋ)

          빨리 짐 빼고 싶으면 비즈니스 / 퍼스트 클라스를 타^^;; 가급적 체크인 카운터 마감 직전에 가는것..?

. push() : 새로운 데이터를 데이터의 최상단에 놓는다.

. top() : 최상단의 데이터를 출력한다.

. pop() : 최상단의 데이터를 출력 -> 제거한다.

---

Queue : 처음 넣은거 처음에 빼고, 나중에 넣은 거 나중에 빼는 것

   eg) 편의점 선입선출, 놀이공원 줄서기 (일상생활에서 가장 익숙한 줄서는 형태)

 

. enqueue() : 데이터 마지막에 새로운 데이터를 추가한다.

. dequeue() : 데이터[front]에 접근하고 -> 삭제한다.

. peek() : 데이터[front]에 접근한다.

. isfull() : 데이터가 가득 찼는지 체크한다; 데이터의 맥시멈사이즈 === 데이터 길이 인지 체크.

. isempty() : 데이터가 비었는지 체크한다 ; 데이터 길이 === 0 인지 체크.

---

Linked list 는 설명을 봐도 이해가 되지 않아, 생활코딩의 linked list 강의를 들었다.

해당 개념을 가장 쉽고 직관적으로 설명한 강의가 아닐까?라고 생각한다!

이 강의는 진짜 명 강의다... 이 링크드 리스트가 이해가 안 되는 사람은 꼭 가서 들어보길 바란다... 최고야!!

 

Linked list : 각각의 동그란 노드들이 다음 노드들과 연결되어 있는 형태

데이터 각각의 '노드'들이 연결되어 있다.

Linked list는 array list 타입과 종종 비교되곤 한다. 비교하여 이해하는 편이 더 이해하기가 쉽다.

 

Array list는 JS 의 배열을 떠올리면 된다. Array list는 공백없이 각각의 엘리먼트들이 다다다닥 연결된 형태.

[0] 10

[1] 88

[2] 3

[4] 110

[5] 2193

[6] 1

 

• 데이터의 최대 공간이 한정되어 있음.
  => 공간이 다 차면, 새로운 공간으로 데이터 전체가 이동하여야 한다.
• 데이터를 추가/삭제할 경우 빈 공간을 허용하지 않기 때문에,
  => [1] 88을 삭제 할경우 3, 110, 2193, 1 등 모든 엘리먼트들의 위치를 수정해줘야 한다 (비효율적)
• 데이터 3을 찾으려면, index를 알고 있을경우 빠르게 찾을 수 있다.

 

Linked list는 array list와 달리,

• 데이터의 최대 공간이 유연하다.
• 데이터를 추가/삭제할 경우 추가할 데이터 앞뒤 데이터를 연결하면 되기 떄문에, 간단하다.
• 데이터 6을 찾기 위해선, 첫번째 데이터부터 6이 나올때까지 하나씩 연결하며 체크해야 하기 때문에 비효율적.

. head() : 헤드 추가 

노드를 생성하고 값을 부여한다 -> 새 노드와 현 헤드(22)를 연결한다 -> 헤드에 새노드값을 대입한다. ->

수정된 전체 노드를 보여준다.

 

. insertion() : 노드 추가

노드를 추가할 위치를 정한다 -> 헤드에 접근한다 -> 노드를 추가할 바로 직전까지 연결 이동한다 ->

바로 직전의 노드를 node1로 지정한다 -> node1의 다음 노드를 2로 지정한다 -> 새노드를 생성하고 값을 부여한다 ->

새노드와 node1을 연결한다 -> 새노드와 node2를 연결한다. -> 수정된 노드를 보여준다.

 

.deletion() : 노드 삭제

노드를 삭제할 위치를 정한다 -> 헤드에 접근한다 -> 노드를 삭제할 바로 직전 데이터까지 연결 이동한다 ->

삭제 직전의 노드를 node1로 지정한다 -> node1의 다다음 노드(삭제할 노드의 다음 노드)를  node2로 지정한다 ->

node1과 node2를 연결한다 -> 삭제할 노드를 삭제한다. -> 수정된 전체 노드를 보여준다.

 

.display() : 노드 전체를 보여준다.

 

.search() : 특정 노드 값을 찾는다. 

헤드에 접근한다 -> 헤드 === 특정 노드 체크한다 -> 맞으면 출력 -> 아니면 다음 노드로 이동한다 ->

찾을때까지 계속 -> 찾으면 출력한다.