자료구조 리스트 이론 조금 (선형리스트, 단순 연결, 이중 연결, 원형 연결,,)

자료구조 어렵다.

이론은 이해가도 코딩으로는 안되는 기적

 

리스트는 목적이 있음

나열되는 순서가 있음

순서가 없다면 리스트가 아닌 그룹임

 

선형리스트 : 자료들 간에 순서를 갖는 리스트

1. 리 2. 스 3. 트

 

리스트 이름 = (원소1, 원소2,,,, 원소n)

 

 

	순차 자료구조	연결 자료구조
메모리 저장 방식	필요한 전체 메모리 크기를 계산하여 할당, 할당된 메모리의 시작 위치부터 빈자리 없이 자료를 순서대로 할당	노드 단위로 메모리 할당 저장 위치 순서 상관X 노드의 링크 필드에 다음 주소 저장
연산 특징	삽입, 삭제 후에도 빈자리 없어야함 변경된 논리 순서 == 저장된 물리 순서	논리적인 순서가 변경되도 링크 정보만 변경되고 물리적인 위치 변경X
프로그램 기법	배열 이용 구현	포인터 이용 구현

 

 

순차 자료구조 문제점

: 연산 작업 후 연속적으로 나열되는 물리 주소를 유지하기 위해서

원소들을 이동시키는 추가적인 작업과 시간이 소요된다. (오버헤드 발생)

ex. 게임 랭킹, 쇼핑몰의 구매 취소 

 

오버헤드(overhead)는 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다.

-> 원소들의 이동 작업으로 인해 생기는 연산 작업들이 많이 발생하면, 성능상의 문제 발생

 

배열의 크기 > 데이터의 수 : 메모리 공간의 낭비

배열의 크기 < 데이터의 수 : 추가 데이터 저장X

-> 배열의 크기에 따른 비효율성 문제

 

배열을 동적으로 생성? (생성 후 자동배열 -> 기존 자료 복사)

복사할 때 드든 자원의 수가 증가하니 잘 구현한게 아님;

 

그래서 연결 자료구조 등장

- 단순 열결, 원형 연결, 이중 연결, 이중 원형 연결

 

 

 

데이터와 링크 => 노드로 구성

데이터 필드(원소 값 저장, 구조체로 복합자료형 구성가능)

 

중간중간에 빈 공간이 있어도 물리적으로는 동일하게 연결되어 있음

 

리스트 week = (1,2,3,4)

리스트 이름 week는 연결 리스트의 시작을 가리키는 포인터변수

=> 첫 번째 노드를 가리키는 동시, 연결 리스트 전체를 의미

 

공백 연결 리스트 : NULL를 저장(널 포인터) -> 아무 노드도 안 가리킴

 

week->data 값을 가리킴 / week->link 주소값을 가리킴

 

 

단순 연결과 이중 연결의 마지막 노드의 링크에는 NULL이 있다.

원형 연결 구조는 자료를 순환해서 탐색할 수 있다는 장점

맨 처음부터 탐색안해도됨, 지금 자신이 있는 위치에서부터 탐색이 가능

 

이중 연결 구조들은 링크에 대한 정보가 2개(이전, 다음)

전방향 탐색 가능, 백워드 탐색 가능 여기서 이중 원형 연결 리스트이면 후방향도 가능 다 가능 가능가능

근데 탐색의 끝은 정해주어야함(While 잘못돌리면 무한루프에 빠짐)

 

for문을 사용안하는 이유

노드의 개수가 저장되어 있어야 사용 가능

카운트라는 저장 변수가 필요하게 됨

while이 더 간단하니까;;

 

원형 연결 리스트의 삭제 연산에는 첫 번째 노드인지 아닌 지를 판단하여 진행해야함

-> 첫 번째면 마지막 링크를 바꿔주는 작업이 필요하기에.

 

배열	연결 리스트
정적, 최대크기 미리 예상 실제로 안 쓰면 공간 낭비	필요에 따라 동적으로 노트 생성 데이터 공간 + 포인터 변수 공간 필요
인덱스 검색으로 바로 검색가능(시간빠름)	헤드부터 포인터를 따라감
오른쪽, 왼쪽 밀림등으로 인해 연산 느림	연산(삽입,삭제)을 인접 노드의 포인터를 변경하니 빠름
검색 위주면 유리	삽입, 삭제위주면 유리 최대 데이터 수가 예측 불가면 유리

 

실습과 코드 이론은 나중에 시험기간의 나를 믿는다.