자료구조

자료구조(資料構造, data structure)란, 자료의 집합을 의미하며 각 원소들 사이의 관계가 논리적으로 정의된 일정한 규칙에 의하여 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 조직적, 체계적으로 구분하여 표현한 것을 말한다.

개요

　자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. 자료구조에는 여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다. 예를 들어 B-트리는 데이터베이스에 효율적이며, 라우팅 테이블은 네트워크(인터넷, 인트라넷)에 일반적이다. 다양한 프로그램을 설계할 때, 어떠한 자료구조를 선택할지는 가장 우선적으로 고려되어야 한다. 이는 큰 시스템을 제작할 때 구현의 난이도나 최종 결과물의 성능이 자료구조에 크게 의존한다는 것을 많은 경험이 뒷받침하기 때문이다. 일단 자료구조가 선택되면 적용할 알고리즘은 상대적으로 명확해지기 마련이다. 때로는 반대 순서로 정해지기도 하는데, 이는 목표로 하는 연산이 특정한 알고리즘을 반드시 필요로 하며, 해당 알고리즘은 특정 자료구조에서 가장 나은 성능을 발휘할 때와 같은 경우이다. 어떠한 경우든, 적절한 자료구조의 선택은 필수적이다. 이러한 관점은 알고리즘보다 자료구조가 보다 중요한 요소로 적용되는 많은 정형화된 개발론 그리고 프로그래밍 언어의 개발을 촉발시켰다. 대부분의 언어는 일정 수준의 모듈개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감춘 채 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. C++, 자바와 같은 객체지향 프로그래밍 언어는 특별히 이러한 목적으로 객체를 사용한다. 이러한 자료구조의 중요성으로 말미암아, 최근의 프로그래밍 언어 및 개발 환경은 다양한 표준 라이브러리를 제공하고 있다. 예로, C++의 표준 템플릿 라이브러리나 자바의 자바 API, 마이크로소프트 .NET과 같은 것들을 들 수 있다. 자료구조에서 가장 기초적인 단위는 행렬, 레코드, 유니온, 참조와 같은 것이다. 예를 들어, Nullable 참조는 참조와 유니온의 조합으로 나타낼 수 있으며, 가장 단순한 자료구조 가운데 하나인 연결 리스트는 레코드와 Nullable 참조로 나타낼 수 있다.

특징

• 효율성(Efficiency)

상황에 맞는 알고리즘을 사용하여 자료를 구조화 시키기 때문에 효율적으로 동작한다. 예를 들어 모든 사원에 대해 사번과 이름의 쌍을 배열이라는 자료구조로 만들었을 때 사번을 가지고 이름을 찾을 경우 배열은 인덱스를 이용하여 데이터를 저장하기 때문에 찾으려는 사번이 첫번째 인덱스에 저장되어 있을 경우 한번의 검색으로 찾을 수 있지만 최악의 경우 제일 마지막 인덱스에 위치할 수 있으므로 데이터의 수만큼 검색을 해야 한다. 평균적으로 자료수/2 만큼의 검색을 해야 하므로 데이터를 찾는 작업이 빈번하고 데이터가 많을 경우 그다지 효율적이지 못하다. 이럴 때에는 해시 테이블과 같은 자료구조를 이용하여 좀 더 빠르게 검색 작업을 할 수 있다. 이처럼 상황에 맞는 적절한 자료구조를 이용하게 되면 데이터 처리의 효율을 높일 수 있다.

• 추상화(Abstraction)

추상화란 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려내는 것을 말한다. 자료구조를 이용하여 데이터를 처리할 경우 처리할 데이터를 어떻게 삽입하고 어떻게 추출할 것인가에 중점을 두지 않는다. 즉, 자료구조 자체를 구현하는 알고리즘에 중점을 두지 않고 어느 시점에 데이터를 삽입할 것이며 어느 시점에 데이터를 추출하고 이러한 데이터를 어떻게 사용할 것인지에 초점을 맞출 수 있기 때문에 프로그램의 비즈니스적인 요소에 좀 더 시간을 할애할 수 있다. 데이터를 처리하는 관점에서 보면 특정 자료구조 자체의 내부 구현은 그리 중요하지 않기 때문에 어떻게 구현했는지 보다 어떻게 사용하는지에 대해서 알고 있으면 된다. 예를 들어 스택(Stack)의 경우 가장 마지막에 삽입한 데이터를 가장 먼저 꺼내는 자료구조이고 push(), pop() 메소드를 통해서 데이터를 삽입하고 꺼낼 수 있다. 그리고 이러한 자료구조의 추상화는 실제 구현한 언어가 무엇인지에 따라 실제 그 코드는 다르지만 추상적인 개념에 대해서만 알고 있으면 되기 때문에 언어에 종속적이지 않다는 특징을 가진다.

• 재사용성(Reusability)

자료구조를 이용하여 데이터를 처리할 경우 해당 자료구조의 인터페이스만 이용하여 데이터를 처리하도록 하므로 모듈화가 가능하다. 이는 자료구조를 설계할 때 특정 프로그램에 맞추어 설계하지 않고 다양한 프로그램에서 사용될 수 있도록 범용화하여 설계함으로써 가능하다.

분류

선형 구조

배열(Array)

• 배열(Array) : 가장 일반적인 구조로써 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료 구조이다.

장단점

• 장점

리스트나 그래프와 같은 자료구조 형태와 달리 탐색없이 인덱스를 통해 직접 액세스 하기 때문에 액세스 속도가 빠르다. 리스트의 경우 10,000 번째 값을 액세스하기 위해서는 첫 번째 값부터 10,000번 탐색해야 하지만 배열의 경우 해당 인덱스 위치의 주소값을 얻는 단 한 번의 연산만으로 액세스가 가능하다.

• 단점

리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 되지 않지만, 배열은 부가 정보 없이 데이터만 저장하기 때문에 기록밀도가 1이다. 리스트나 그래프는 메모리에 분산시켜 데이터를 저장하고 포인터로 연결시킨 형태여서 데이터 외 부가 정보를 가지게 된다. 반대로 배열은 메모리의 연속된 공간에 데이터를 저장하고 인덱스를 이용한 연산을 통해 액세스하기 때문에 부가 정보가 필요 없다.

연결리스트(Linked List)

• 연결리스트(Linked List) : 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

장단점

• 장점

링크로써 구현되어있기 때문에, 자료를 추가하거나 삭제할 시에 링크만 바꿔주면 되기 때문에 추가, 삭제가 용이하다.(추가 원소 이동 연산이 불필요하다.)
메모리 효율성이 우수하다.
필요할 때마다 데이터 추가, 삭제할 수 있기 때문에 배열 리스트처럼 최대 원소 개수 지정이 필요 없다.

같이 보기

• C언어
• 자바
• 파이썬
• 객체지향 프로그래밍
• 프로그래밍 언어

이 자료구조 문서는 프로그래밍에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

개발 : 프로그래밍 □■⊕, 소프트웨어, 데이터, 솔루션, 보안, 하드웨어, 컴퓨터, 사무자동화, 인터넷, 모바일, 사물인터넷, 게임, 메타버스, 디자인 프로그래밍 언어 ASP • C 언어 • C++ • C# • CSS • D 언어 • HTML • HTML5 • JSP • PHP • R • XHTML • XML • XSLT • 고(Go) • 고급언어 • 기계어 • 델파이 • 러스트 • 루비 • 루아 • 리액트 • 리퀴디티 • 무브 • 미켈슨 • 베이직 • 브이비스크립트 • 비주얼 C++ • 비주얼베이직(VB) • 비주얼베이직닷넷(VB.NET) • 솔리디티 • 스몰토크 • 스위프트 언어 • 스칼라 • 스크립트 언어 • 알골 • 어셈블리 • 언리얼스크립트 • 얼랭 • 에이잭스(Ajax) • 엠에프씨(MFC) • 오브젝티브-C • 오브젝트 파스칼 • 오카멜 • 웹어셈블리(WASM) • 이와즘(eWASM) • 자바 • 자바스크립트 • 저급언어 • 제이슨(JSON) • 제이쿼리(jQuery) • 카멜 • 코볼 • 코틀린 • 콜드퓨전 • 타입스크립트 • 파스칼 • 파워스크립트 • 파이썬 • 펄(Perl) • 포트란 • 프로씨(Pro-C) • 피엘에스큐엘(PL/SQL) • 피엘원(PL/I) • 하스켈 개발방법론 CBD 개발방법론 • EA • 구조적 개발방법론 • 객체지향 개발방법론 • 라이브러리 • 람다 아키텍처 • 모듈 • 모듈화 • 벤치마킹 • 소프트웨어 개발방법론 • 스크럼 • 스프린트 • 아키텍처 • 아키텍트 • 애자일 • 웹개발방법론 • 정보공학 개발방법론 • 컴포넌트 • 테일러링 • 템플릿 • 폭포수 모델 • 프로젝트 • 프로토타입 • 피드백 코딩 EUC-KR • UTF-8 • 값 • 글루웨어 • 노팔로우 링크 • 두팔로우 링크 • 디버깅 • 디코딩 • 마크업 • 버그 • 부트스트랩 • 세이브포인트 • 소스코드 • 시큐어코딩 • 아스키 • 액티브엑스 • 오픈소스 • 유니코드 • 인코딩 • 재컴파일 • 주석 • 컴파일 • 컴퓨터 프로그램 • 코드 • 코딩 • 태그 • 테스트 • 테이블 • 텍스트 • 파싱 • 퍼블리싱 • 퓨니코드 • 하드코딩 • 하이퍼링크 • 하이퍼텍스트 프로그래밍 C 명령어 • 객체 • 객체지향 • 객체지향 프로그래밍 • 거짓 • 관계연산자 • 기본형 변수 • 널 • 논리 • 논리연산 • 논리연산자 • 다중상속 • 다형성 • 대입 • 대입문 • 대입연산자 • 더블 • 도스 명령어 • 디폴트 • 레지스터변수 • 루프 • 리눅스 명령어 • 리턴 • 메모리 주소 • 메소드 • 멤버 • 명령문 • 명령어 • 무한루프 • 문자 • 문자열 • 바이트 • 반복문 • 배열 • 변수 • 분기 • 분기문 • 불린 • 브레이크 • 비교연산자 • 비트연산자 • 산술연산자 • 상속 • 상수 • 생성자 • 선언 • 선언문 • 설정자 • 속성 • 스위치 • 스태틱 • 시프트연산자 • 실행 • 실행문 • 어노테이션 • 에코 • 역참조 • 연산 • 연산문 • 연산자 • 오버로딩 • 오버라이딩 • 외부변수 • 윈도우 명령어 • 유닉스 명령어 • 인스턴스 • 인스트럭션 • 인클루드 • 인터페이스 • 임포트 • 입력 • 입력문 • 입출력 • 입출력문 • 자료형(데이터 타입) • 자바 명령어 • 자바 예약어 • 자바 컬렉션 • 전역변수 • 접근자 • 접근제어자 • 정보은닉 • 정수형 • 정적변수 • 제어 • 제어문 • 제어자 • 조건 • 조건문 • 조건연산자 • 주소 • 증감연산자 • 지역변수 • 참 • 참조 • 참조변수 • 초기화 • 추상메소드 • 추상클래스 • 추상화 • 출력 • 출력문 • 캡슐화 • 케이스 • 클래스 • 파라미터(매개변수) • 파이널 • 패키지 • 퍼블릭 • 포인터 • 프라이빗 • 프로텍티드 • 필드(멤버변수) • 함수 • 환경변수 명령어 abstract • array • boolean • break • byte • case • char • continue • default • double • do while • echo • elif • else • else if • false • final • float • for • gosub • goto • if • if else • import • include • int • join • long • long long • null • print • printf • println • private • protected • public • return • scanf • short • stdio.h • static • string • switch • temp • then • true • unsigned • void • while 디자인패턴 구조패턴 • 동시성패턴 • 동시실행패턴 • 모델-뷰-컨트롤러 패턴 • 상태패턴 • 생성패턴 • 싱글톤패턴 • 아키텍처패턴 • 전략패턴 • 커맨드패턴 • 행동패턴 프로그래밍 인물 귀도 반 로썸 • 그레이스 머레이 호퍼 • 니클라우스 비르트 • 댄 브릭클린 • 더그 커팅 • 데니스 리치 • 리누스 토르발스 • 리처드 그린블라트 • 마거릿 해밀턴 • 마크 앤드리슨 • 빈트 서프 • 빌 게이츠 • 빌 조이 • 스티브 잡스 • 에이다 러브레이스 • 제임스 고슬링 • 척 벤턴 • 켄 톰슨 • 팀 패터슨 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반