배열과 연결리스트

배열

정의

자료형이 같은 데이터 여러개를 하나의 변수 이름에 인덱스를 가지고 일렬로 저장하는 자료의 집합체

 

종류

1차원 배열

인덱스 하나를 사용해서 데이터에 접근하는 배열

데이터들이 컴퓨터 메모리에 물리적으로 연속해서 할당되고 연속해서 저장된다.

 

다차원 배열

인덱스 여러 개를 사용해서 데이터에 접근하는 배열

동일한 크기의 1차원 배열을 여러개 사용하는 배열 

바둑판 모양을 가진다.

데이터들이 컴퓨터 메모리에 물리적으로 연속해서 할당되고 연속해서 저장된다.

1. 열 우선 순서

2, 행 우선 순서

 

연결리스트

정의

데이터 필드와 링크 필드를 가지고 포인터 변수를 사용해서 노드 간을 연결하는 리스트

 

종류

단일 연결 리스트

후행 노드만을 가리키는 링크

필드를 1개 가지는 연결리스트

후행노드에는 접근하기 쉽지만 선행노드에는 접근 할 수 없다.

헤드노드부터 새로 시작해야 한다.

 

이중 연결리스트

두개의 링크 필드를 가지고 하나는 선행 노드를 또하나는 후행 노드를 가리키는 연결 리스트

선행 노드와 후행 노두 모두 접근하기 쉽다.