[자료구조] Linked List

본 내용은 인하대학교 겨울 계절학기 자료구조 수업 내용 기반입니다.

Array와 Linked List

Array는 임의의 인덱스에 빠르게 접근이 가능하다. 하지만 메모리 크기가 제한되어 있기 때문에 미리 할당한다. 반면 Linked List는 사이즈를 동적으로 바꿀 수 있고 있다. 하지만 임의에 노드에 접근하기 위해서는 앞에서부터 순차적으로 접근해야 한다.

Singly Linked List

싱글 링크드 리스트에 관한 설명을 이미지로 나타낸 것이다. element가 담긴 data칸이 존재하고 다음 노드에 관한 주소에 대한 정보가 담긴 next칸이 있다.

Add Head

void StringLinkedList::addFront(const Elem& e)
{
	StringNode* v = new StringNode;
    if(empty()) tail = v;
    v->elem = e;
    v->next = head;
    head = v;
}

Remove Head

void StringLinkedList::removefront()
{
	if(empty()) return;
    StringNode* old = head;
    head = old->next;
    delete old;
    if(empty()) tail = NULL;
}

Add Tail

void StringLinkedList::addBack(const Elem& e)
{
	StringNode* v = new StringNode;
    v->elem = e;
    v->next = NULL;
    if(empty()) head = tail = v;
}

Remove Tail

void StringLinkedList::removeBack()
{
	if(empty()) return;
    StringNode* current = head;
    
    if(current == tail) {
    	head = tail = NULL;
        delete current;
    }
    
    else {
    	while(current != tail) {
        	current = current->next;
        }
        tail = current;
        delete tail->next;
        tail->next = NULL;
    }
}