자료구조 및 실습 - [3] 기초 데이터 구조 (배열, 연결리스트) (1)

데이터 구조의 기본 재료

데이터를 구성하는 기본 재료로는 배열과 연결리스트가 존재한다. 이는 고급 데이터구조를 구축하는 기본 재료로 쓰이기 때문에 잘 알아두어야 한다!

---

배열 (array)

순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터 원소들

배열은 1차원 뿐만 아니라 N차원 배열이 존재한다.

다차원 배열

2차원 배열은 pandas의 DataFrame과 같은 모양이다. 테이블(table)이라고도 불리며 1차원과 2차원은 각각 행(row)과 열(Column)로도 불린다.

3차원 배열은 2차원 배열이 여러 개 합쳐있는 것이다. (ex. 4분기별 세 학생의 8과목에서의 점수)

4차원 배열은 3차원 배열이 여러 개 합쳐있는 것이다. (ex. 3년간 4분기별 세 학생의 8과목에서의 점수)

 

---

연결리스트 (Linked list)

동적메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터원소의 노드들

연결 리스트의 종류
- 단일연결리스트(singly linked lists)
- 이중연결리스트(doubly linked lists)
- 원형연결리스트(circularly linked lists)
- 헤더및트레일러연결리스트(linked lists with header and trailer)
- 이들의 복합

데이터 원소의 노드라고 표현되었는데 노드란 무엇일까?

노드(node): 한개의 데이터 원소를 저장하기 위해 동적메모리(dynamic memory)에 할당된 메모리

이며, 연결 리스트의 종류에 따라 노드의 구성이 약간씩 달라진다.

 

단일 연결리스트

단일연결리스트를 구성하는 노드

단일연결리스트란 연속노드로 구성된, 가장 단순한 연결데이터 구조이다. 노드는 위와 같이 원소와 링크로 구성되어있고, 원소는 데이터를 링크는 다음 노드의 주소를 저장한다.  위와 같은 노드가 여러 개로 연결되며 단방향으로만 이동할 수 있다. 

단일연결리스트의 구조

다음 노드가 없는 경우는 널링크를 저장하며, 접근점은 첫 노드 즉, 헤드노드의 주소이다.

 

이중 연결리스트

이중연결리스트의 노드

이중연결리스트는 추가 링크를 사용하여 역방향 순회도 가능하다. 따라서 노드의 구성도 달라지게 된다.

노드는 데이터를 저장하는 원소, 다음 노드의 주소를 저장하는 링크, 추가로 이전 노드의 주소를 저장하는 링크로 구성되어 있다.

양방향으로 움직일 수 있기 때문에, 접근점은 헤드노드(Head node)의 주소 또는 테일노드(Tail node)의 주소이다.

이중연결리스트의 구조

 

원형 연결리스트

원형 연결리스트란 마지막 노드의 링크가 헤드노드의 주소를 가리키는 연결리스트이다.

원형연결리스트를 구성하는 노드

노드는 단일연결리스트와 같은 구조를 가지고 있고, 전체 구조를 보면 다음과 같다.

원형연결리스트의 구조

 

헤더와 트레일러

헤더와 트레일러는 헤드노드 바로 앞에 헤더 혹은 테일노드 바로 뒤에 트레일러 노드를 추가하여 작업 편의성을 높일 수 있다. 헤더와 트레일러에는 dummy element를 저장한다. 이론적으로 보면 왜 작업 편의성이 증진되는지 감이 잘 안오지만, 구현해보면 헤더와 트레일러 노드가 있다면 굉장히 편안한 것을 느낄 수 있다.

헤더가 있는 단일연결리스트

이외에도 여러 연결리스트가 있다.

원형 헤더 연결리스트(circular header linked lists)
원형 이중연결리스트 (circular doubly linked lists)
헤더 및 트레일러 이중연결리스트
헤더 및 트레일러 원형 이중연결리스트