0. 자료구조

자료구조란 자료를 쉽게 관리하기 위해 다양한 구조로 묶는 것이다.
다양한 자료구조가 존재하며, 각 자료구조마다 효율적인 관점에서 장점과 단점이 존재한다.

자료구조에는 크게 두가지 구조가 있다.

1) 선형 자료구조

자료를 순차적으로 나열 (데이터를 일렬로 나열된 형태로 저장)

  • (정적)배열
    : 생성될 때 저장공간의 크기가 고정되는 배열
    => 데이터 추가(append) 불가
  • 동적배열
  • 연결리스트

2) 비선형 자료구조

하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

  • 트리
  • 그래프

1. ADT(Abstract Data Type)

먼저 추상화란 필요한 부분, 중요한 부분을 통합하여 하나로 만드는 것을 말한다.
[도형], [세 개의 각], [세 개의 변] 이 세 가지 내용은 모두 '삼각형'과 관련된 것이다.
나열되어 있는 세 가지 요소들을 일일히 언급하지 않고, '삼각형'이라고 부르는 것이 추상화의 한 예라고 할 수 있다.

추상자료형(ADT)이란, 자료와 연산자의 특성을 논리적으로 추상화하여 정의한 자료형이다.

추상자료형(ADT)는 추상적으로 필요한 기능을 나열한 일종의 명세서(로직)이며, 기본자료형(리스트, 숫자, 문자열 등)을 활용하여 사용자에 의해 구현된다.
자료구조의 방법이 코드로 정의된 것이 아니라 그 행동 양식이 정의된 것이다.
각 규칙을 이해하면 직접 ADT 스택, 큐, 연결리스트 자료구조를 만들 수 있을 것이다.



2. Linked-list (연결리스트)

2.1. 연결 자료구조

  • 연속한 물리주소에 의해 원소의 순서를 표현한 것이 아니라, 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식이다.
  • 원소의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.
  • 여러 개의 작은 공간을 연결하여 하나의 전체 자료 구조를 표현한다.
    => 크기 변경이 유연하고 좀 더 효율적인 메모리 사용이 가능

2.2. 연결 리스트

연결리스트란 리스트를 연결 자료구조로 표현한 구조이다.
연결 방식에 따라 다음과 같은 종류가 있다.

  • 단순 연결 리스트
  • 원형 연결 리스트
  • 이중 연결 리스트
  • 이중 원형 리스트
  • etc..

연결리스트는 말 그대로 리스트들을 연결해준다.
연결은 프로그래밍에서 참조의 기능으로 구현되고, 연결리스트는 리스트의 길이를 별도로 지정해줄 필요가 없다.
또한, 아래 그림처럼 연결리스트는 별도의 인덱스를 지정할 필요 없이 연결되는 구조다.

2.3. 연결 리스트의 노드

연결 리스트의 노드는 연결 자료구조에서 하나의 원소를 표현하기 위한 단위이다.
연결 리스트의 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성되며, <원소, 주소>단위로 저장된다.

데이터 필드(data field)
: 원소의 값을 저장, 원소의 형태에 따라 하나 이상의 필드로 구성

링크 필드(link field)
: 다음 노드의 주소를 저장하는 곳으로, 포인터 변수를 사용하여 주소값을 저장한다. 포인터 또는 링크 또는 참조라고 일컫는다.

연결리스트의 각 요소는 참조하는 노드에 저장된다.
각 노드는 연결리스트의 다음 노드에 대해 참조(또는 '포인터')를 한다.




created on Nov 24, 2021

  • 글 작성

0개의 댓글