배열, 연결리스트
- 배열(array) : 순차 기억장소에 할당된 유한 개수의 동일 자료형 데이터원소들
- 베이스(base) : 배열의 첫째 셀 위치
- 오프셋(offset) : 해당 셀이 베이스로부터 떨어진 거리(변위차)를 나타내는 정수형
- 2차원 배열 : 테이블(table)이라고도 불림, 1차원과 2차원은 각각 행(row)과 열(column)로도 불림
이번 게시글에서는 자료구조를 구축하는 바탕인 배열과 연결리스트에 대해서 살펴보겠습니다. 자료구조는 비교적 추상적인 반면, 배열과 연결리스트는 상대적으로 구체적(컴퓨터 구조에 가까움)이기 때문에 자료구조를 배열과 연결리스트로 구현하게 됩니다.
배열은 비교적 간단한 개념인데요. 쉽게 이야기하면 데이터를 순차적으로 메모리에 배치한 자료구조 라고 할 수 있습니다. 오프셋(offset)이라는 개념은 원래 “동일 오브젝트 안에서 오브젝트 처음부터 주어진 지점까지의 변위차를 나타내는 정수형” 인데요, 일반적으로 배열에서는 베이스로부터 떨어진 거리를 나타냅니다. 소스 코드를 컴파일 할때, 배열의 셀들은 베이스(base)부터 시작하여 차례로 메모리에 할당됩니다.
- 연결리스트(linked list)
- 정의 : 동적메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터원소 노드들
- 연결리스트 이름(linked list name) : 연결리스트의 시작 위치, 즉, 첫 노드의 주소
- 연결리스트 크기(linked list size) : 연결리스트내 노드 수
- 노드(node) : 한 개의 데이터원소를 저장하기 위해 동적 메모리(dynamic memory)에 할당된 메모리
- 동적 메모리(dynamic memory) : 프로그램 실행시 프로그램에 의해 사용가능한 주 메모리의 구역
- 연결리스트의 종류
- 단일연결리스트(singly linked lists)
- 이중연결리스트(doubly linked lists)
- 원형연결리스트(circularly linked lists)
- 헤더 및 트레일러 연결리스트(linked lists with header and trailer) 등
연결리스트에 대해서 알아보겠습니다. 연결리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다. 정확한 이해를 돕기 위해, 구체적인 예를 살펴보겠습니다.
- 단일연결리스트
- 연속 노드로 구성된, 가장 단순한 연결 데이터구조
- 노드 저장내용
- 원소(element): 데이터원소
- 링크(link): 다음 노드의 주소 – 다음 노드가 없는 경우 NULL 저장
- 접근점 : 헤드노드(head node)의 주소
- 이중연결리스트
- 추가 링크를 사용하여 역방향 순회도 가능
- 노드 저장내용
- 원소(element): 데이터원소
- 링크(link): 다음 노드의 주소, 이전 노드의 주소
- 접근점 : 헤드노드(head node)의 주소, 테일노드(tail node)의 주소
- 원형연결리스트
- 마지막 노드의 링크가 헤드노드의 주소
- 접근점 : 헤드노드의 주소
- 헤더와 트레일러
- 헤드노드 바로 앞에 특별한 헤더(header) 노드를 추가하여 작업 편의성을 증진
- 같은 목적으로 테일노드 바로 뒤에 트레일러(trailer) 노드 추가 가능
- 특별노드 저장내용 : 모조 원소(dummy element)
- 접근점 : 헤더노드(또는 트레일러노드)의 주소
연결리스트를 종류별로 간단히 시각화하면 위와 같이 표현할 수 있습니다. 연결리스트는 일반적으로 구조체로 노드를 만든 다음, 포인터를 이용하여 노드를 연결하는 방법으로 구현됩니다. C언어를 이용하여 구현하는 방법은 다음 게시글에서 살펴보도록 하겠습니다.
* 이 게시글은 데이터구조 원리와 응용(국형준, 21세기사)을 읽고 개인 학습용으로 정리한 내용입니다.
'학습 정리 > 🦴 CS Study' 카테고리의 다른 글
| 2. 소프트웨어 보안, 악성 코드 (0) | 2022.12.11 |
|---|---|
| 1. 정보보호 및 컴퓨터 보안 개념 (0) | 2022.12.11 |
| [자료구조] - 4. 추상자료형, 리스트 ADT (0) | 2022.04.16 |
| [자료구조] - 2. 재귀 (0) | 2022.04.15 |
| [자료구조] - 1. 개요, 원시작업, Big-Oh 표기법 (0) | 2022.04.15 |