연결리스트로 구현한 스택 스택을 구현하는 데 있어서 연결리스트를 활용할 수 있습니다. 연결리스트로 스택을 구성하면 배열로 구성된 스택에 비해 크기의 제한이 없다는 장점이 있지만 반대로 메모리를 동적으로 할당하므로 할당과 해제에 따른 시간이 소모된다는 단점이 있습니다. 삽입 연산 연결리스트로 구현된 스택에 노드를 삽입하는 연산의 경우 다음 두 순서의 변경 사항이 필요합니다. 1. temp(삽입할 노드)의 link를 top으로 할당. 2. top을 temp로 할당. 이때 순서가 변경되어서는 안됩니다. 만약 top을 temp로 할당하는 과정을 먼저 수행하면 temp의 link가 가리킬 위치를 알 수 없게됩니다. 삭제 연산 연결리스트로 구현된 스택에 노드를 삭제하는 연산의 경우 다음 두 순서의 변경 사항이 필요..

이중 연결리스트 이중 연결리스트는 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 리스트입니다. 아래 그림처럼 노드의 왼쪽 링크(left link)와 오른쪽 링크(right link)가 각각 다른 노드의 오른쪽 링크와 왼쪽 링크를 연결짓고 있으며 특별하게 헤드도 노드로 이루어져 있습니다. 헤드노드 헤드노드는 데이터를 가지지 않고 오로지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드입니다. 따라서 헤드 포인터와의 구별이 필요하며 리스트가 공백상태라면 헤드 노드만 존재하는 상태입니다. 이때 헤드노드의 left link는 right link를 가리키며 right link는 left link를 가리키는 상태입니다. 삽입 연산 new_node를 before의 앞쪽에 삽입하는 연산입니다. (1)은 ..

원형 연결리스트 원형 연결리스트에서 head 포인터는 마지막 노드를 가리키게 됩니다. 이러한 방식의 원형 리스트는 head는 마지막 노드를, head의 link는 첫 노드를 가리키므로 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리해집니다. 앞부분 삽입 연산 노드를 리스트의 첫 부분에 삽입하는 연산의 경우 두 가지의 변경 사항이 필요합니다. 1. node의 link를 head의 link로 할당 2. head의 link를 node로 할당 [중요] 이때 순서가 변경되어서는 안됩니다. 만약 2를 먼저 실행, 즉 head의 link를 먼저 변경해버리면 node의 link를 지정해 줄 주소를 알 수 없게됩니다. // 앞 삽입 ListNode* insert_first(ListNode* head, elemen..

단순 연결리스트를 이용한 다항식과 계산 구현 8x^12 + (-3x^10) + 10x^6과 같이 여러개인 수식을 다항식이라 부릅니다. 단순 연결리스트를 통해서 다항식을 구현할 수 있습니다. 다항식 구현에는 특수한 헤더 노드가 추가로 사용됩니다. 헤더 노드의 헤드는 리스트의 앞부분을, 테일은 리스트의 끝부분을 가리키도록 합니다. #include #include // 노드의 타입 typedef struct { int coef; int expon; struct ListNode* link; } ListNode; // 리스트 헤더의 타입 typedef struct { int size; ListNode* head; ListNode* tail; } ListType; // 오류 함수 void error(char* me..

연결리스트로 구현된 리스트 연결리스트(Linked List)는 리스트의 항목들을 노드(node)에 분산하여 저장하는 리스트입니다. 노드의 구성으로는 데이터 필드와 링크 필드가 있습니다. 데이터 필드 : 리스트의 원소, 즉 데이터 값을 저장하는 곳 링크 필드 : 다른 노드의 주소값을 저장하는 장소 (포인터) 연결리스트의 장점으로는 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없고 크기 제한이 없다는 점이 있습니다. 반면에 단점으로는 구현이 어렵고 까다로우며 오류가 발생하기 쉬운 점이 있습니다. 연결리스트의 종류에는 단순 연결리스트, 원형 연결리스트, 이중 연결리스트가 존재합니다. 단순 연결리스트는 가장 끝의 노드는 항상 NULL을 가리키게 되며 원형 연결리스트는 NULL이 위치한 곳이 없습니다. 이중..

리스트 리스트란 n개의 element형으로 구성된 순서 있는 모임을 말합니다. 리스트를 구현하는 방법에는 배열을 이용한 구현과 연결리스트를 이용한 구현이 있습니다. 리스트 Abstract Data Type insert(list, pos, item) ::= pos 위치에 요소를 추가한다. insert_last(list, item) ::= 맨 끝에 요소를 추가한다. insert_first(list, item) ::= 맨 처음에 요소를 추가한다. delete(list, pos) ::= pos 위치의 요소를 제거한다. clear(list) ::= 리스트의 모든 요소를 제거한다. get_entry(list, pos) ::= pos 위치의 요소를 반환한다. get_length(list) ::= 리스트의 길이를 구한..