-
정의
- 컴퓨터에서 다양한 자료를 더욱 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용 용도를 고려해, 조직적, 체계적으로 구분하여 표현한 것
분류
- 크게 선형구조와 비선형구조로 나눌 수 있다.
출처-미래창조과학부 선택기준
- 자료의 처리시간, 크기, 활용빈도, 갱신정도, 프로그램의 용이성
활용
- 주로 데이터의 정렬, 검색, 파일 편성 및 인덱스 등에서 주로 이용
배열(Array) 리스트의 표현, 다항식의 덧셈 문제의 해결, 희소행렬 등 리스트 배열의 구현, DBMS Index, 탐색이나 정렬과 같은 문제 등 스택(Stack) 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 후위 표기법 연산, 텍스트 에디터 undo 기능 등 큐(Queue) 운영체제의 작업 스케줄링, 대기 행렬의 처리, 비동기 데이터 교환(File I/O, Sockets, Pipes), 키보드 버퍼, Spool 등 트리 탐색이나 정렬과 같은 문제, 문법의 파싱, 허프만 코드, 결정 트리, 게임 등 그래프 컴퓨터 네트워크(근거리 통신망, 인터넷, 등), 전기회로 분석, 이항 관계, 연립 방정식 등
배열(Array)
- 메모리 상의 원소를 연속하게 배치한 자료구조
0 1 2 3 4 5 6 7 8 9 2 4 13 5 -44 31 24 85 31 0 배열의 성질
- O(1)에 n번째 원소에대한 확인 및 변경, 원소의 마지막에 추가 및 제거가 가능, O(n)으로 임의의 위치에 원소를 추가 및 제거를 할 수 있다.
- 추가적으로 소모되는 overhead가 거의없다.
- 메모리에서 연속 구간을 잡아야한다 → 메모리 할당에 제약
배열의 선언과 접근 방법 
결과 2차원 배열
2차원 배열의 선언과 접근 방법 
결과
연결리스트(Linked List)
- 각 노드가 데이터와 포인트를 가지고 한 줄로 연결시키며 자료를 저장하는 구조
- 배열과 비교하였을 때 삽입, 삭제시 O(1)이므로 구조의 재구성에 용이함, 단 원하는 위치를 알고 있을 경우
- 알지 못하는 경우는 O(1)이라 할 수 없다.
- 데이터 검색시 O(n)으로 연결리스트를 처음부터 끝까지 순회해야 하므로 배열보다 비효율적이다.
- 배열을 이용한 구현 방법, 구조체와 포인터를 이용한 구현 방법이 있다.
- 원소들이 메모리 상에서 연속해있지 않아 할당이 배열보다 쉽다.
연결리스트 종류
Single Linked List 
각 노드가 다음 노드에 대해서만 참조하는 단순한 형태의 연결리스트.
큐 구현시 사용, Head를 참조하지 못할 경우 연결리스트 전부 사용 불가.
Doubly Linked List 
각 노드가 이전 노드, 다음 노드에 대해 참조하는 형태의 연결리스트.
삭제가 간편하며 Single에 비해 데이터 손상에 강하다. 하지만 prev, next 작업을 둘다 해줘야 한다.
Circular Linked List 
마지막 노드가 처음 노드를 참조하는 형태의 연결리스트.
연결리스트 구현
연결리스트를 위한 기본 노드 설정 
연결리스트 상에서 노드를 연결하는 방법 
임의의 위치에 있는 노드의 연결을 끊는 경우 
마지막에 존재하는 노드의 연결을 끊는 경우 
기존 노드의 데이터를 검색하는 경우 
구현 결과