호기심 많은 오리의 지식 저장소 호기심 많은 오리의 지식 저장소

맨 마지막 노드의 포인터가 다시 첫 노드를 가리키는 연결 리스트 구조이다. 단순 연결 리스트에서는 이전에 위치한 노드를 탐색할 수 없다. 원형 연결 리스트에서는 이전 노드까지 계속 반복문을 돌다 보면 이전 노드에 도착할 수 있어서 편리하다. 목적지까지 한 번만 운행하는 열차와, 같은 구간을 도는 순환 열차를 생각하면 되겠다. 이번에는 헤드 포인터(Head pointer)를 사용해서 구현하는 법을 정리해 보겠다. 참고로 헤드 포인터란, 원형 연결 리스트 구조체 안에서 노드를 가리키는 포인터이다. 원형 연결 리스트는 맨 마지막 노드가 첫번째를 가리킨다는 조건이 있으므로, 노드의 삽입과 삭제 기능을 구현할 때 주의 해야 한다. ※ 밑에 헤드 포인터의 타입은 CircularListNode* 임. 현재 그림에 C..

연결 리스트에서 각 요소는 노드(Node)로 이루어 진다. 노드는 구조체로 구현하며, 데이터와 다음 노드를 가리키는 포인터로 이루어 져 있다. 단순 연결 리스트는 이전 노드 안에 있는 포인터가 다음 노드를 가리키는 구조로 되어 있다. 마지막 노드의 링크는 NULL을 가리키며 뒤로 돌아갈 수 없다. 만약 어떤 노드로 돌아가기 원한다면 맨 처음 노드로 다시 설정하여 순회(iteration) 하여야 한다. 연결 리스트를 구현 하는 방법은 두 가지가 있는데, 하나는 더미 노드(Dummy Node)를 이용하는 방법이고 하나는 헤드 포인터(Head Pointer)를 사용하는 방법이다. 더미 노드란, 데이터 저장을 위한 노드가 아니라 노드의 추가/삭제 구현의 간편성을 위해 사용하는 노드이다. 실제 데이터를 저장하는 ..

연결 리스트(LinkedList)는 서로 떨어져 있는 메모리 공간을 포인터를 사용해 연결시켜 놓은 자료 구조이다. 배열리스트는 배열(Array)를 이용하기 때문에 처음에 정해 놓은 메모리 공간에서 벗어날 수 없지만(지정해놓은 배열의 최대 크기를 벗어날 수 없다) 연결 리스트(LinkedList)는 그런 한계 없이 자유롭게 노드를 추가할 수 있다. 물리적 메모리 공간에서, 배열 리스트와 연결 리스트가 메모리를 점유한 모습이다. 배열 리스트는 배열을 사용해 순차적으로 메모리 공간을 사용하지만, 연결 리스트는 그렇지 않다는 점을 보여준다. 연결 리스트는 포인터를 사용하기 때문에 데이터를 빈번하게 삽입, 삭제해야 하는 상황에서 상당히 유연하게 움직인다. 해당 노드의 링크만 연결해주고, 끊어주면 되기 때문에 삽입..

배열 리스트(Array List)는 배열(Array)을 사용하는 선형 자료구조이다. 배열과의 차이점은, 배열은 중간에 데이터를 빼면 빈 공간이 생겨 메모리 공간이 낭비될 수 있지만, 배열 리스트는 순차적으로 저장된다는 리스트의 특성을 가지고 있기 때문에 중간에 공간이 뻥 하고 뚫려 메모리가 낭비되는 일은 없다. 위의 그림을 살펴보면 6개짜리 char 배열이 생성되어 있는 것을 확인할 수 있고 그 안에는 A부터 F까지 알파벳으로 초기화 되어 있다. 배열의 특징을 가지고 있기 때문에 리스트의 원소(element)에 접근하기 위해서는 배열의 인덱스(index) 값으로 접근하여야 한다. 이러한 특성 때문에 특정 원소에 접근할 때 빠른 속도로 접근할 수 있다. 다만 추가, 삭제가 자주 일어날 경우 해당 인덱스 뒤..

리스트 (List) : 자료를 차례대로 저장하는 자료 구조. 선형 자료구조의 특징이 있음. 리스트의 추상자료형 (ADT) 주의점 : 리스트의 인덱스 (index) 는 항상 0부터 시작한다.

자료구조 : 컴퓨터에서 자료를 효율적으로 저장하는 방식. 자료구조가 효율적이면 실행시 메모리를 절약할 수 있고 실행시간을 최소화 시킬 수 있다. 1) 단순구조 프로그래밍 언어에서 제공하는 기본적인 타입. int, float, double, char 등... 2) 선형 구조 각각의 자료들 사이의 앞뒤 관계가 1:1인 경우. 3) 비선형 구조 각각의 자료들 사이 앞뒤 관계가 계층 구조(Hierarchical Structure) 혹은 망 구조(Network Structure)를 가지는 경우 4) 파일 구조 보조기억장치에 저장되는 파일에 대한 구조 추상자료형 (ADT, Abstract Data Type) : 추상적으로 정의된 자료형. 정보 은닉을 사용하여 자료구조를 간단하게 나타낸다. 정보 은닉을 사용하여 사용..

알고리즘 = 어떠한 문제를 해결하기 위한 여러 동작들의 집합. 알고리즘의 조건 입력 : 외부에서 제공되는 자료가 0개 이상 있어야함.출력 : 적어도 1개 이상의 결과를 만들어 내야 함.명확성 : 각 명령어는 의미가 모호하지 않고 명확해야 함유한성 : 한정된 수의 단계 뒤에는 반드시 종료됨. 무한히 동작해서는 안됌. 유효성 : 모든 명령은 실행 가능한 연산 이어야 함. 알고리즘을 표현 하는 법 자연어 : 사람이 사용하는 일반적인 언어로 표현순서도(Flow Chart) : 그림으로 도식화 해서 표현의사코드 (Pseudo Code) : 특정 프로그래밍 언어가 아니라 가상의 언어로 표현.프로그래밍 언어 : 프로그래밍 언어로 표현. 알고리즘의 분석 기준 1) 시간 복잡도 (Time Complexity) 알고리즘 ..