자료구조

자료구조

자료구조란 ?

자료를 효율적으로 저장하고 사용하기 위해서 자료의 특성에 따라 분류하고 구성하고 저장 및 처리하는 모든 작업

자료구조의 종류

- 단순구조 : 정수, 실수, 문자, 문자열 . . . ( 하나의 값만을 저장하고 다른데이터와의 관계성 X )

- 선형구조 : 자료들간의 앞뒤 관계가 1:1 인 선형관계 ( ex 리스트, 연결리스트, 스택, 큐 . . )

- 비선형구조 : 자료들간의 앞뒤 관계가 1:N 또는 N:M인 관계 ( ex 트리, 그래프 . . )

노드 ( NODE )

데이터, 다른 노드와의 관계를 저장할 공간 등을 포함하고 있는 클래스로 구현한다.

데이터 필드 / 링크 필드

리스트

유한한 원소의 나열된 묶음 : 인접리스트, 연결리스트

- 인접리스트 (= 선형리스트, 순차리스트 )

: 데이터의 순서와 같게 메모리에 저장이 된다.

: 논리적 순서와 물리적 순서가 같다.

: 논리적인 순서에 맞춰서 물리적인 위치가 결정이 된다.

- 순차 자료구조의 문제점

삽입 연산이나 삭제 연산 후에 연속적인 물리주소를 유지하기 위해 원소들을 이동시키는 추가적인 작업이나 시간이 소요된다. -> 성능 저하로 직결

더보기 각 Node 마다 index를 하나씩 할당해 주어야한다. 생성자를 선언하게 되면, Node에 할당된 data / index 의 값들은 비워진채로 만들어진다 . data = ' ' (데이터는 생성자에서 만들어지기에 생략가능 ) -> 생성자에서 변수는 만들어지기에 아래와 같이 인덱스 할당을 순서대로 적용해주면 된다. 노드를 만들면서 data를 하나씩 추가해주는 과정 ( 아래 ) #삽입 ( idx 1 -> 'C' ) 의 과정 결과 #삭제의 과정

위와 같은 문제를 해결해기위해 --> '연결리스트' 가 등장함

- 연결리스트

'자료의 논리적 순서와 물리적 순서가 일치하지 않는 구조'

각 노드에 저장되어 있는 다음 노드의 주소값에 의해 순서가 결정된다. -> 따라서 물리적인 순서를 맞출 필요가 없다.

여러개의 작은 공간들을 연결하여 전체 구조를 표현한다.

728x90

from http://daily50.tistory.com/240 by ccl(A) rewrite - 2021-08-08 11:00:49