[자료구조] 배열, 연결 리스트

[ 자료구조 ]

데이터 값의 모임

-> 메모리 공간을 효율적으로 사용해야 할 때 필요

 

[ 배열(Array) ]

 같은 종류의 데이터를 순차적으로 저장하는 자료 구조

고정된 크기를 갖고 있음

인덱스(Index) 번호로 데이터에 접근할 수 있다.

 

 

배열

요소(element): 배열을 구성하는 각각의 값

인덱스(Index): 데이터를 기록할 경우 그 데이터의 이름, 데이터의 크기 등의 속성과 그 기록 장소 등을 표로 표시하는 것. 0부터 시작, 배열의 크기 - 1까지 사용할 수 있다.

 

-> 참조용 데이터

 

 

[ C# 배열 선언 및 초기화 ]

int[] arr = new int[] { 0, 1, 2 };

int[] arr2 = { 0, 1, 2 };

int[] arr3;
arr3 = new int[] { 0, 1, 2 };

 

 

[ 특징 ]

고정된 크기: 배열은 고정된 크기를 가지므로, 배열의 크기를 변경하려면 배열을 재할당해야 한다.

순차적인 저장: 배열은 데이터를 순차적으로 저장. 따라서 인덱스를 사용하여 데이터에 빠르게 접근할 수 있다.

같은 종류의 데이터: 배열은 같은 종류의 데이터만 저장할 수 있다. 

인덱스: 배열은 인덱스를 사용하여 데이터에 접근. 

 

- 장점

빠른 접근, 간단한 구현

 

- 단점

고정된 크기, 메모리 낭비

 

 배열은 순차 접근이 자주 발생하는 작업에 적합하다.

리스트, 큐, 스택과 같은 데이터 구조를 구현하는 데 사용됨.

 

 

[ 연결 리스트(Linked List) ]

 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조

데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와 연결을 담당한다.

크기가 가변적이다.

 

 

연결 리스트

헤드 노드(Head node): 연결 리스트의 첫 번째 노드

노드(node): 데이터와 다음 노드에 대한 포인터를 포함하는 데이터 구조

포인터(pointer): 다음 노드의 주소를 저장하는 변수

테일 노드(Tail node): 연결 리스트의 마지막 노드

 

 

[ C# 연결리스트 선언 및 초기화 ]

LinkedList<int> list = new LinkedList<int>();

// 데이터 추가
list.AddLast(0);
list.AddLast(1);
list.AddLast(2);

 

[ 특징 ]

- 장점

데이터의 추가와 삭제가 자유로움

데이터의 크기가 제한되지 않음

메모리 사용량이 적음

 

- 단점

데이터의 탐색이 느림

데이터의 정렬이 어려움

 

연결 리스트는 데이터의 추가와 삭제가 자주 발생하거나 데이터의 크기가 제한되지 않은 경우에 적합하다.

웹 브라우저의 히스토리, 운영 체제의 프로세스 목록, 텍스트 편집기의 문자열 목록 등에 사용된다.