재민

Linked List에서 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다. 2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다. 3) 삭제할 노드를 삭제하고, 메모리를 해제한다. 삭제 연산을 c로 구현하면 다음과 같다. #include #include // 단일 연결 리스트의 노드 정의 struct Node { int data; struct Node* next; }; // 연결 리스트의 헤드를 전역 변수로 선언 struct Node* head = NULL; // 연결 리스트에 노드 추가 void insertNode(int val) { str..

연결 리스트에서 삽입은 어느 위치에 노드를 삽입하느냐에 따라 다르다. [중간 노드 삽입] 1. 삽입할 노드를 준비한다 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 삽입할 위치 앞 노드의 링크값이 된다. 4. 삽입할 위치 앞 노드에 새 노드를 연결한다. [첫번째 노드 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 head가 가리키고 있는 노드의 주소값이 된다. 4. head에 새 노드를 연결한다. [마지막 노드로 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드가 마지막 노드이므로 링크값으로 NULL을 지정한다. 4...

리스트는 자료를 구조화하는 가장 기본적인 방법으로서, 값들을 나열한다. 리스트에서는 새로운 항목을 리스트의 처음, 중간,끝에 삽입하여 저장할 수 있다. 그리고 리스트의 특정 부분을 추출하거나 특정 값을 삽입 혹은 삭제할 수 있다. 리스트는 구현이 간단하지만 삽입 삭제시 오버헤드가 발생할 가능성이 있는 Linear List와, 삽입 삭제가 효율적이지만 구현이 복잡한 Linked List로 나뉜다. Linked List에서 한 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시켜야만 한다. 삽입을 위해서는 먼저 원소를 삽입할 빈 자리를 만들어서, 빈 자리에 원소를 삽입한다. (빈 자리를 만들기 위해 기존의 원소들은 한칸씩 뒤로 이동시킨다) 즉 n+1개의 ..

Linked list를 통한 다항식의 표현과정은 크게 두가지이다. 1) 다항식의 모든 항을 배열에 저장함으로써 구현하는 방법 다항식의 각종 연산이 간단해진다는 장점이 있다. 해당 항의 값을 추출하여 연산하면 되기 때문이다. 그러나 대부분의 항의 계수가 0이면 공간 낭비가 심해진다는 단점을 갖고 있다. 이를 극복하기 위한 방법으로 다음 방법을 쓴다. 2) 다항식의 계수가 0이 아닌 항만을 배열에 저장하는 방법 하나의 배열로 여러 개의 다항식을 나타낼 수 있는 방법이다. 메모리 공간 측면에서는 효율적이지만, 다항식의 연산이 복잡해진다.