자료구조 강의 5화 :: 배열 리스트, 포인터 리스트

자료구조 5화를 듣고 배운내용

 

 

KEYWORDS

리스트: 원소들 간의 순서가 지켜지며 유지되는 자료구조

리스트 원소들 간의 순서: 데이터가 저장되는 물리적 위치와 상관없이 사람들 머리속에 인식되는 논리적인 순서 혹은 리스트에 나타나는 원소들 간의 의미적인 순서

리스트의 노드: 원소값과 다음 원소를 가리키는 위치의 주소값으로 구성된 자료단위. 데이터 요소와 리스트의 다음 요소를 지시하는 포인터를 가지는 자료단위

포인터: 메모리에 저장되는 데이터의 저장 위치에 대한 주소를 가리키는 데이터형

단항 연산자: 피연산자 하나만 갖는 연산자

구조체(struct): 다양한 데이터형의 변수를 하나의 상자 안에 넣어서 선언해서 사용하는 C 프로그램이 문법

 

 

배열로 만든 리스트 보다 포인터로 만든 리스트가 좋다는걸 알게 된다고 한다

 

리스트

일정한 순서의 나열

메인 메모리 상에는 들쭉날쭉 저장되어 있다.

포인터 or 배열을 이용해서 수서대로 가져와서 본다.

 

 

배열을 이용한 리스트

• 원소 삽입시, 오른쪽으로 쭉 하나씩 밀어야 된다.
• 크게 만들어 놨으면 그만큼 메모리 낭비
• 원소 삭제시, 앞으로 댕겨야 된다.
• 이런 이동들이 프로그램 수행시간을 증가시킨다

 

포인터를 이용한 리스트

노드의 연결로 만든다.

노드: 값과 다음 주소값을 가진 자료단위

 

 

노드의 삭제

노드 A, B, C가 있으면

A => B => C

A   ==>     C

이렇게 이어 버린다

 

 

노드의 삽입

노드 A, B가 있고 새 노드 X를 삽입하려면

A => B 에서 중간에 넣고 싶다면,

A => X => B로 이어 버리면 된다.