자료구조 정리

알고리즘 공부에 앞서 자료구조들의 기본적인 특징을 정리하고자 합니다.

---

리스트

리스트는 총 3종류의 리스트를 정리합니다.

링크드 리스트, 더블 링크드 리스트, 환형 링크드 리스트

 

링크드 리스트

데이터와 포인터로 이루어진 노드를 연결하여 만든 리스트로

각 노드가 다음 노드를 가르키는 포인터를 갖고 있는 구조로 이루어져 있으며 

마지막 노드를 테일, 첫번쨰 노드를 헤더라 부르며 리스트의 시작이 되는 주소값이 헤더에 들어가 있다.

 

첨부. 링크드 리스트 구조

장점으로는

• 새로운 노드의 추가/삽입/삭제가 쉽고 빠릅니다.

단점으로는

• 다음 노드를 가리키려는 포인터 떄문에 각 노드마다 추가적인 메모리(4byte)가 소모된다.
• 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도가 느리고
  , 노드의 갯수가 n개인 경우 최악일때 n번의 노드 탐색 루프가 발생한다.

결론은 "새로운 데이터의 추가/삽입/삭제는 빠르나 특정 위치에 있는 데이터를 찾는 연산은 느리다,

따라서 링크드 리스트는 추가/삽입/삭제가 잦고 조회가 드문 로직에 사용되는게 유리하다."

 

더블 링크드 리스트

링크드 리스트가 한방향으로만 데이터를 탐색할 수 있었다면 더블 링크드 리스트는 

한 노드에 앞 노드, 뒷 노드를 가르키는 포인터를 가지고 있어 양방향으로 탐색이 가능하다.

링크드 리스트와 마찬가지로 첫번째 노드를 헤드, 마지막 노드를 테일이라 칭한다.

첨부. 더블 링크드 리스트 구조

특징은 링크드 리스트의 단점을 보완하고자 만들어 졌으며 한방향으로 순차적으로 조회하던 방식에서

양방향으로 조회가 가능해져 조회 하는 로직에 있어서 사용방식에 따라 최대 2/n의 탐색의 효율을 얻을 수 있으나.

추가/삽입/삭제의 과정에 드는 비용이 더 발생한다 - 한노드당 4byte의 메모리가 추가로 소진된다.

 

환형 링크드 리스트

환형 링크드 리스트는 헤더노드의 앞 노드는 테일노드의 포인터 정보를 가지고 있다.

즉 헤더노드만으로 테일노드의 위치를 알 수 있다.

첨부. 환형 링크드 리스트 구조

특징으로는

• 반복적인 순회에서 연결리스트의 끝을 체크해야할 필요가 없음
• head같은 메타데이터가 필요하지 않음
• 이로인해 시간, 메모리, 코드 모두 이득을 볼 수 있음
• ex) 같은 리스트 데이터를 계속 출력하는 로직

---

스택

처음 들어온 데이터가 가장 나중에 나가는 선입후출 FILO(First In, Last Out)의 구조를 지닌다.

 

장점으로는

• 자료의 조회가 빠르다.
• 선입후출의 구조라 메모리제어, 수식계산(후위표기법으로), 지역변수저장 등의 처리에 유리하다.
• 후위표기법링크(https://jamanbbo.tistory.com/53)

 

단점으로는

• 처음 발생하는 데이터가 오랫동안 존재할 수 있는 경우가 생긴다. (메모리 관리 관점에서 골칫덩이인 데이터)
• 선입후출의 구조로 우선순위와 관련된 작업에 사용할 수 없다.

 

첨부. 스택구조

---

큐

처음 들어온 데이터가 먼저 나오는 선입선출 FIFO(FIrst In First Out)의 구조를 지닌다.

 

순환큐

원형의 구조를 가진 큐로 데이터가 순환하는 구조다.

 

장점으로는 

• 직선큐보다 성능이 좋으며 삽입, 삭제가 빠르다.

단점으로는

• 용량이 제한되어 있으며 가득차 있는 상태와 비어있는 상태를 구별할 수 없다.

첨부. 순환 큐

직선 큐

직선 모양의 구조를 가진 큐로 데이터가 순환되지 않는다.

 

장점으로는 

• 데이터의 용량을 미리 정할 필요가 없다.
• 우선순위 관련된 작업에 최적화 되어 있다. (스케줄링, 프린터 우선순위 작업 등)

 

단점으로는

• 데이터가 많아질 수 록 데이터 삭제에 불리하다.
• (데이터 삭제 시 n개의 데이터의 경우 n-1번의 이동이 필요하다.)

첨부. 직선 큐

---

트리

나무모양을 닮은 자료구조로 검색엔진, Html Dom구조 등 다양한 예제에서 사용 된다.

뿌리, 가지, 잎 구조를 가지고 있으며 각각 최상의 노드, 중간 노드, 최하위 노드를 편의상 부르는 명칭이다.

노드표현,중첩된 집합,중첩된 괄호 표현 등으로 표기할 수 있다.

 

이진트리

(참고 블로그 : https://sonman.tistory.com/manage/newpost/15?type=post&returnURL=https%3A%2F%2Fsonman.tistory.com%2F15)

한 노드가 최대 2개의 자식을 가질 수 있는 구조의 트리다.

순회방식이 뿌리부터 하위까지 탐색하는 전위, 잎부터 시작하는 중위(수식 트리에 사용 된다.), 전위와 반대되는 후위 순회 방식이 있다.