[데이터베이스] 자료구조의 개념 및 리스트(List)의 특징(선형 구조)

자료구조(Data Structure)란

 

프로그램 구동을 위해 필요한 자료들을 어떻게 저장공간에 저장할지와 저장된 자료들을 어떤 형태로 있는지 그리고 어떤 방법으로 처리를 하는지를 다룹니다. 자료구조를 통해 일련의 자료들을 조직하고 구조화하며 자료구조가 잘 되어 있으면 성능 등에 크게 영향을 미치게 됩니다.

 

우리는 자료구조를 활용해 정렬(Sort), 검색(Search), 저장 방식 지정, 인덱스(Index) 등을 진행합니다,

정렬(Sort)은 기억장치에 무작위 하게 정렬되어 있는 자료들을 사용자가 지정한 순서에 맞게 나열을 하는 것을 의미합니다.

검색(Search)은 기억장치 내에 위치한 자료를 찾는 것을 의미합니다.

저장 방식 지정은 기억장치에 저장할 때 어떤 구조로 파일을 저장할지 지정하는 것을 의미합니다.

인덱스(Index)는 파일에서 특성 자료를 빠르게 찾기 위해 색인을 지정하는 방식을 의미합니다.

 

그렇다면 자료구조의 종류에는 어떤 게 있을지 알아보도록 하겠습니다.

자료구조는 크게 구분하면 선형 구조와 비선형 구조로 분류가 되고 각각의 구조에는 아래와 같은 자료구조들이 있습니다. 

구분	자료구조 종류
선형 구조	리스트(선형 리스트, 연결 리스트)
	스택(Stack)
	큐(Queue)
	데크(Deque)
비선형 구조	트리(Tree)
	그래프(Graph)

모든 자료구조들을 포스팅 하기에는 너무 길어지니 오늘은 리스트에 대하서만 안내드리겠습니다.

 

우선, 선형 리스트(Linear List)는 배열(Array)과 같이 연속되는 기억 장소에 저장하는 것을 의미합니다. 배열은 가장 대표적인 선형 리스트입니다. 선형 리스트는 다음과 같은 특징이 있습니다.

장점	가장 간단한 자료 구조
	인덱스를 직접 선택하여 해당 위치에 있는 값에 접근을 쉽게 할 수 있음
	기억 장치를 연속으로 사용해서 저장 공간 밀도는 1로 가장 좋음
단점	연속적으로 자료들이 나열되어 있어 중간에 값을 삽입하려면 빈 공간을 만들어야 됨
	자료를 삽입 및 삭제하면 나머지 자료들의 이동이 필요해서 손이 많이 감

삽입과 삭제의 예를 들면

배열 A가 [0, 1, 2, 3, 5, 6]으로 구성되어 있고 4번째와 5번째(코딩 시 인덱스는 0부터 시작해서 3번째와 4번째가 됨) 사이에 4를 집어넣는다면 5와 6이 위치한 자료의 위치를 뒤로 한 칸씩 이동을 시켜주고 4를 삽입해야 됩니다. 이동하는 작업 없이 4를 삽입하면 삽입하려는 위치에 있는 값이 4로 변하고 기존 값은 사라지기 때문입니다. 물론 삭제할 때도 같습니다. 값을 삭제하면 다음에 위치한 값들을 앞으로 옮겨주는 작업을 진행해야 됩니다.

 

다음은 연결 리스트(Linked List)입니다. 

연결 리스트는 자료들을 연속적으로 배열하지는 않고 기억공간에 임의로 저장을 하지만 노드의 포인터(값이 위치한 주소를 가리키는 기능)라는 기능으로 서로 연결시킨 구조를 말합니다. 연결 리스트는 다음과 같은 특징을 가집니다.

장점	새로운 값을 삽입하거나 삭제가 편함
	연속적인 구조를 취할 필요가 없음
단점	주소를 가리키는 노드 포인터를 지정해야 하며 퍼져 있는 자료들은 기억장치의 효율을 떨어 뜨림
	중간의 노드 포인터가 주소를 잃어버리면 다시 지정을 해줘야 함
	포인터의 주소값을 확인 후 다음 값을 찾아가서 효율이 안좋음

노드: 자료를 저장하는 데이터 부분과 다음 노드를 가리키는 포인터로 구성이 되어 있음

포인터: 현재의 위치에서 다음 노드의 위치를 알려주는 기능을 함

 

연결 리스트의 종류로는 단순 연결 리스트(Singly Linked List), 단순 환상 연결 리스트(Singly Circular Linked List), 이중 연결 리스트(Doubly Linked List) 및 이중 환상 연결 리스트(Doubly Circular Linked List)가 있습니다.

단순 연결 리스트는 포인터가 다음의 값만을 가리기고 있는 리스트를 의미합니다.

<단순 연결 리스트>

단순 환상 연결 리스트는 단순 연결 리스트와 유사하지만 마지막 값과 붙어있는 포인터가 제일 처음 시작한 값을 가리켜 순환을 하는 형태의 리스트를 의미합니다.

<단순 환상 리스트>

이중 연결 리스트는 노드 포인터를 2개씩 가지고 있어서 전 후 주고 받았던 주소 값을 모두 가지고 있는 구조를 의미합니다.

<이중 연결 리스트>

 

이중 환상 연결 리스트는 이중 연결 리스트 구조에 제일 마지막 주소가 제일 앞 주소까지 가리키는 구조를 의미합니다.

<이중 환상 연결 리스트>

이상으로 리스트에 대한 포스팅을 마치겠습니다.

 

스택, 큐, 데크, 트리 등에 대한 내용이 궁금하시면 아래의 링크를 참고 부탁드립니다.

2022.10.22 - [Intelligence Technology] - [데이터베이스] 자료구조 - 스택(Stack), 큐(Queue), 데크(Deque)의 개념 및 처리 방법 비교

[데이터베이스] 자료구조 - 스택(Stack), 큐(Queue), 데크(Deque)의 개념 및 처리 방법 비교

2022.10.23 - [Intelligence Technology] - [데이터베이스] 자료구조 - 트리(Tree)의 개념(비선형 구조)

[데이터베이스] 자료구조 - 트리(Tree)의 개념(비선형 구조)

2022.10.23 - [Intelligence Technology] - [데이터베이션] 자료구조 2진 트리 및 이진 탐색 트리

[데이터베이션] 자료구조 2진 트리 및 이진 탐색 트리

 

오늘도 똑구의 꿀팁 블로그를 방문해 주셔서 감사합니다.