티스토리 뷰

연결리스트는 동적인 데이터를 처리하는 것과 관련된 수많은 문제의 근간을 이루는 자료 구조이다.


연결리스트의 종류

  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List

  • Singly Linked List
리스트의 다음 원소에 대한 연결고리가 들어있다.
리스트의 마지막 원소는 꼬리라고 부르며, 연결고리는 비워두거나 null로 지정한다.

앞으로만 Traversal할 수 있다. So, 리스트를 완전 종주하려면 항상 첫 번째 원소부터 시작해야 한다.
So to speak, 리스트에 있는 모든 원소의 위치를 파악할 때 리스트의 첫 번째 원소에 대한 포인터나 레퍼런스가 있어야만 한다. 
그포인터나 레퍼런스는 보통 별도의 자료구조에 저장한다.

  • Doubly Linked List
이중 연결 리스트는 단일 연결 리스트의 여러 가지 단점을 극복하기 위해 만들어진 것.
어느 방향으로든 종주할 수 있다.

  • Circular Linked List
원형 연결 리스트에는 끝, 즉 머리나 꼬리가 없다.
원소가 하나밖에 없는 리스트라면 그냥 자기 자신을 가리키면 된다.
(주의) 원형 연결 리스트의 종주(travelsal) 문제를 따질 때는 무한루프가 생기지 않도록 주의해야한다. 시작점을 제대로 파악해놓지 않으면 리스트를 한없이 돌게 된다.

  • 기초연산
  1. 머리 원소 추적
  2. 리스트 종주
  3. 원소의 삽입 및 삭제

1.머리 원소 추적

단일 연결 리스트에서는 반드시 머리 원소를 추적해야 한다.
(주의) head 포인터앞에 새로운 head를 만들고싶을때 function's parameter로 double pointer를 써야한다. 그렇지 않으면 head 포인터에 대한 지역 변수 사본만 갱신하기 때문에 제대로 작동하지 않는다.(포인터값이 call-by-value로 복사되기 때문이다.)

2.리스트 종주
첫 번째 원소가 아닌 원소에 대한 연산을 하려면 리스트의 원소중 일부를 종주해야 할 수 있다.
(주의)이과정에서 항상 리스트가 끝나지 않는지 확인을 해야 한다.

3.원소의 삽입 및 삭제
삭제 및 삽입을 하려면 삽입 또는 삭제할 위치 바로 앞에 있는 원소에 대한 포인터 또는 레퍼런스가 필요하다.



스택 구현법


문제: 스택 자료 구조에 대해 논하라. 연결 리스트, 또는 동적 배열(dynamic array)을 써서 C로 스택을 구현해 보고 그 자료 구조를 사용한 이유를 설명하라. 완전하고 일관적이고 사용하기 편리한 스택 인터페이스를 설계하라. 


Stack
  • LIFO: Last-In-First-Out 자료구조이다.
  • 원소를 삽입하고 삭제하는 연산은 보통 각각 push와 pop이라고 부른다.
  • 스택을 여러 개의 sub task로 나뉘는 task를 관리하는 데 유용하게 쓰이는 자료구조
  • 스택을 사용하는 대표적인 예로 서브루틴에서 사용할 반환 주소, 매개 변수, 지역 변수 등을 추적하는 것을 들 수 있다.
  • 또 다른 예로는 프로그래밍 언어를 파싱할 때 토큰을 추적하는 것을 들 수 있다.

*동적 배열의 연결 리스트에 대한 상대적인 장점
  • 배열 원소에 대한 임의의 접근이 가능함(인덱스만 알면 어떤 원소든 즉시 액세스 가능)
=>하지만, 스택에 대한 연산은 항상 자료구조의 한쪽 끝(스택 맨 위)에 대해서만 이뤄지기 때문에 동적 배열의   "임의접근성" 이라는 장점이 별 힘을 발휘할 수 없다. 또한 배열이 커짐에 따라 크기 조절 및 모든 원소의 새 배열이동이 필요하기에 시간이 오래 걸릴 수 있다.


push 연산
  1. 새로운 원소 할당
  2. 메모리 할당 과정에서 문제가 없었는지 확인
  3. 새로운 원소의 데이터를 설정
  4. 스택 맨 위에 놓은 다음 스택 포인터를 조정
pop 연산
  1. 스택이 비어있진 않은지 확인
  2. 맨 위에 있는 원소의 데이터를 가져옴
  3. 스택 포인터 변경
  4. 더 이상 스택에 들어있지 않은 원소의 메모리 할당을 해제

연결 리스트를 사용하여 스택을 구현 하는 데 있어서 꼭 필요한 것은 아니지만 완벽한 인터페이스 설계를 위해 createStack과 deleteStasck함수도 만들어 두면 좋다.(동적 배열을 써서 스택을 구현할 때는 이 함수들을 꼭 만들어야 가능성이 높다.

createStack
  • 스택을 값으로 반환할 수 없기 때문에 스택에 대한 포인터의 포인터를 인자로 받아와야 한다.

deleteStack
  • 스택을 값으로 반환할 수 없기 때문에 스택에 대한 포인터의 포인터를 인자로 받아와야 한다.
  • pop함수를 반복적으로 호출해도 되겠지만, 연결 리스트를 종주하면서 각각을 쭉 비워줘도 된다.


객체지향 언어를 사용한다면 인터페이스를 훨씬 더 깔끔하게 설계할 수 있다. 
  • createStack과 deleteStasck 연산은 각각 생성자와 파괴자에서 처리한다.
  • push와 pop루틴은 스택 객체와 연관되어서 작동할 것이기에 스택을 인자로 전달하지 않아도되고, 포인터에 대한 포인터를 넘긴다거나 하지 않아도 된다.
  • 메모리 할당이 제대로 안되면 예외 상황을 던지면 된다.

/* stack_implementation.cpp */



#include <iostream>
using namespace std;


typedef struct Element{
struct Element *next;
void* data;
} Element;

bool push(struct Element** stack, void* data);
bool pop(struct Element** stack, void** data);
bool createStack(struct Element** stack);
bool deleteStack(struct Element** stack);


bool push(struct Element** stack, void* data)
{
Element *newElem = new Element;
if(!newElem) return false;
newElem->next = *stack;
newElem->data = data;
*stack = newElem;
return true;
}
 
bool pop(struct Element** stack, void** data)
{
if(!(*stack)) return false;
void* returnData = (*stack)->data;
Element *deleteElem = *stack;
*stack = (*stack)->next;
free(deleteElem);
*data = returnData;
return true;
}

bool createStack(struct Element** stack)
{
Element *newElem = new Element;
if(!newElem) return false;
*stack = newElem;
(*stack)->next = NULL;
return true;
}

bool deleteStack(struct Element** stack)
{
if(!(*stack)) return false;
Element* top = *stack;
while(top)
{
if((*stack)->next) top = *stack;
free(*stack);
*stack = top;
}
return true;
}

int main(int argc, char *argv[]) {
return 0;
}



/* stack_class.cpp */


#include <iostream>


using namespace std;


class Stack{

public:

Stack();

void push(void* data);

void* pop();

~Stack();

protected:

class Element{

public:

Element(Element* n, void *d): next(n), data(d) {}

Element* getNext() const { return next; }

void* value() const { return data; }

private:

Element* next;

void* data;

};

private:

Element* head;

};


Stack::~Stack()

{

while(head)

{

Element *next = head->next;

delete head;

head = next;

}

}


void Stack::push(void* data)

{

Element *elem = new Element(head, data);

head = elem;

}


void* Stack:: pop()

{

Element *delElem;

void* returnData;

if(!head)

{

delElem = head;

head = head->getNext();

returnData = delElem->value();

free(delElem);

}

return returnData;

}



int main(int argc, char *argv[]) {

}



연결 리스트의 꼬리 포인터


문제: 정수를 저장하기 위한 어떤 단일 연결 리스트의 첫 번째와 마지막 원소를 가리키는 head와 tail이라는 전역 포인터가 있다.다음과 같은 함수 원형에 대한 C 함수를 구현하라.

  bool delete(Element *elem);
  boolinsertAfter(Element *elem, int data);

delete 함수의 인자는 삭제할 원소다. insertAfter 함수의 두 인자는 각각 새로 추가되는 원소의 바로 앞 원소에 대한 포인터와 새로 추가될 원소의 데이터이다. insertAfter 함수를 호출할 때 NULL을 넘겨주는 방식으로 리스트 맨 앞에도 새 원소를 추가할 수 있어야 한다. 함수가 성공적으로 실행되면 true를, 그렇지 않으면 false를 반환한다. 

머리(head)와 꼬리(tail) 포인터는 항상 최신 값으로 유지해야 한다.


긴 리스트의 중간에서 작업을 할때는 머리와 꼬리에 영향을 미치지 않는다. 리스트의 맨 앞, 또는 맨 뒤에 있는 원소가 바뀔 때만 바꿔주면 된다.

연산 처리 케이스
  • 일반 케이스: 리스트 중간에서 원소를 삽입/삭제하는 경우
  • 특별 케이스: 맨 앞 또는 맨 뒤에서 원소를 삽입/삭제하는 경우
  • 특별 케이스: 리스트의 길이에 따라(0,1,2)


/*Linked List's head and tail pointer*/

/*

정수를 저장하기 위한 어떤 단일 연결 리스트의 첫 번째와 마지막 원소를 가리키는 head와 tail이라는 전역 포인터가 있다.

다음과 같은 함수 원형에 대한 C 함수를 구현하라.


bool delete(Element *elem);

boolinsertAfter(Element *elem, int data);


delete 함수의 인자는 삭제할 원소다. insertAfter 함수의 두 인자는 각각 새로 추가되는 원소의 바로 앞 원소에 대한 포인터와 새로 추가될 원소의 데이터이다. insertAfter 함수를 호출할 때 NULL을 넘겨주는 방식으로 리스트 맨 앞에도 새 원소를 추가할 수 있어야 한다. 함수가 성공적으로 실행되면 true를, 그렇지 않으면 false를 반환한다. 


머리(head)와 꼬리(tail) 포인터는 항상 최신 값으로 유지해야 한다.


*/

#include <iostream>

using namespace std;


typedef struct Element{

struct Element* next;

int data;

}Element;


bool deleteElement(Element *elem);

bool insertAfter(Element *elem, int data);


Element* head;

Element* tail;


bool deleteElement(Element *elem)

{

//Traverse the whole list from head to tail

Element* curElem = head;

if(!curElem) return false;

if(curElem == elem) //elem is very the head pointer.

{

head = curElem->next;

free(curElem);

if(!head) tail = NULL;

return true;

}

while(curElem)

{

if(curElem->next == elem)

{

curElem->next = elem->next;

if(curElem->next == NULL) tail = curElem;

free(elem);

return true;

}

curElem = curElem->next;

}


return false;

}


bool insertAfter(Element *elem, int data)

{

Element* curElem = head;

Element* newElem = new Element;

newElem->data = data;

if(!newElem) return false;

if(!head)

{

tail = head = newElem;

tail->next = NULL;

return true;

}

/* 리스트의 맨 앞에 삽입하는 경우 */

if(elem == NULL)

{

newElem->next = head;

head = newElem;

/* 비어있는 리스트의 경우 */

if(!tail) tail = newElem;

return true;

}

while(curElem)

{

/*curElem 자신과 elem을 비교함으로써 맨처음에 head와 elem을 비교할 필요가 없어졌음.*/

if(curElem == elem)

{

newElem->next = curElem->next;

curElem->next = newElem;

if(!(newElem->next))// that is the last element

{

tail = newElem;

}

return true;

}

curElem = curElem->next;

}

if(curElem == elem)

{

elem->next = curElem->next;

curElem->next = elem;

if(elem->next == NULL) tail = elem;

return true;

}

while(curElem)

{

if(curElem->next == elem)

{

newElem->next = elem->next;

elem->next = newElem;

if(newElem->next == NULL)

{

tail = newElem;

}

return true;

}

curElem = curElem->next;

}

/* 삽입할 위치를 못 찾은 경우, 할당된 메모리를 비우고 false를 반환한다. */

free(newElem);

return false;

}



int main(int argc, char *argv[]) {

return 0;

}





removeHead의 버그


문제: 단일 연결 리스트에서 맨 앞에 있는 원소를 제거하기 위한 용도로 만들어진 다음 C 함수에 있는 버그를 찾아내어 수정하라.

void removeHead(ListElement *head){
free(head); // 첫째 줄
head = head->next; //둘째줄
}



버그를 찾아내는 문제도 드물지 않게 나오는 편이기 때문에 이런 유형의 문제에 적용할 수 있는 일반적인 전략을 파악해보자.

보통 주어지는 코드의 분량이 적기 때문에 실제 프로그래밍을 할 때 버그를 잡아내는 방법하고는 조금 다른 전략을 적용해야 한다. 대신 디버거를 쓰지 않고 함수에 있는 각 줄을 체계적으로 분석해야 한다.
  1. 데이터가 함수에 제대로 들어오는 지 확인한다. : 없는 변수를 쓰려고 한다고나, 타입이 잘못되었거나, 작업을 수행하는데 필요한 모든 값들이 준비되어있는지 확인
  2. 함수의 각 줄이 제대로 작동하는지 확인한다. : 의도된 결과가 만들어지는지 확인
  3. 함수에서 데이터가 올바르게 나오는지 확인한다. : 예상되는 결과가 반환 값으로 돌아가야 한다. 그리고 함수를 호출한 쪽의 변수를 갱신해야 한다면 그 작업이 제대로 이뤄지는지도 확인하자.
  4. 흔히 발생하는 오류 조건을 확인한다. : 오류 조건은 문제에서 주어진 요구사항에 따라 다양하게 달라질 수 있다. 오류는 주로 특이한 인자 값과 연관되어 발생한다. 예를 들어, 자료 구조에 대한 연산을 수행하는 함수의 경우에는 비어있는, 또는 거의 비어있는 자료 구조를 다룰 때 문제가 생기는 경우가 많다. 포인터를 인자로 받아들이는 함수의 경우에는 NULL 포인터가 들어왔을 때 제대로 작동하지 않을 수 있다.

#include <iostream>

/*
단일 연결 리스트에서 맨 앞에 있는 원소를 제거하기 위한 용도로 만들어진 다음 C 함수에 있는 버그를 찾아내어 수정하라.

void removeHead(ListElement *head){
free(head); // 첫째 줄
head = head->next; //둘째줄
}
*/

typedef struct ListElement{
struct ListElement *next;
void* data;
} ListElement;
 
void removeHead(ListElement **head){
ListElement *tmpElem;
if( head && (*head))
{
tmpElem = (*head)->next;
free(*head);
(*head) = tmpElem;
}
}

using namespace std;
int main(int argc, char *argv[]) {
}


연결 리스트의 마지막에서 m번째 원소


문제: 단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번째 원소를 찾아내는 알고리즘을 만들어 보라. 이때 시간 및 공간 효율을 모두 고려해야 한다. 오류 조건의 처리에 주의하여 알고리즘을 구현하라. 여기에서 "맨 뒤에서 m번째 원소"는 m = 0일 때 리스트의 마지막 원소를 반환하는 식으로 생각한다.



  • 뒤에서 m번째 원소를 찾는 일을 자주 해야하는 경우라면 단일 연결 리스트 말고 다른 자료 구조를 쓰는 것이 훨씬 나을 것이라는 의견을 피력하고 싶을 수도 있다. 실제 프로그램을 구현할 때는 당연히 다른 자료 구조를 쓰는 것이 효율적인 해결책이지만, 면접 문제에서는 주어진 그대로 풀라는 주문을 할 것이다.
  • 원소의 개수를 현재 알고리즘에서 따로 구해야 한다면 연결 리스트 전체를 거의 두 번 완전히 종주해야만 한다.  메모리에 제약이 있는 시스템에서는 매우 큰 리스트가(디스크에 저장된) 페이지 아웃된 가상 메모리에 들어가 있을 가능성이 매우 높다. 그런 경우에 리스트를 한 번 완전히 종주하려면 리스트를 조금씩 순서대로 스와핑해서 메모리에 올리는 작업을 하면서 디스크에 여러번 액세스해야 한다. 이런 상황에서는 똑같은 O(n) 알고리즘이라고 해도 리스트를 한 번만 종주하면 되는 것과 두 번 종주해야 하는 것 사이의 속도 차가 상당히 크다.
  • 현재 원소를 머리 위치에 추가하고 꼬리에 있는 원소를 제거하는 식으로 원소의 개수가 m개인 큐를 계속 유지하면 그 큐의 마지막 원소는 언제나 현재 위치로부터 m 원소만큼 앞에 있는 원소가 되도록 만들 수 있기 때문이다.

#include <iostream>
using namespace std;
/*
단일 연결 리스트가 주어졌을 때 리스트의 맨 뒤에서 m번째 원소를 찾아내는 알고리즘을 만들어 보라. 이때 시간 및 공간 효율을 모두 고려해야 한다. 오류 조건의 처리에 주의하여 알고리즘을 구현하라. 여기에서 "맨 뒤에서 m번째 원소"는 m = 0일 때 리스트의 마지막 원소를 반환하는 식으로 생각한다.
*/

typedef struct Element{
struct Element *next;
void* data;
} Element;

bool findMToLastElement(Element *list, int m, Element* rv){
int i = 0;
Element *mHead, *mTail ;
if( !list || (m < 0) ) return false;
mTail = list;
for(i = 0 ; i< m ; i++){
if(list->next){
list = list->next; 
}else{
return false;
}
}
mHead = list;
while(mHead->next){
mHead = mHead->next;
mTail = mTail->next;
}
rv = mTail;
return true;
/*
if(!list || (m < 0)) return false;
while(list){
if( (m - cnt) <= 0 ){
if(!mHead)
mHead = mTail = list;
else
mHead = list;
}
else{
mHead = mHead->next;
mTail = mTail->next;
}
cnt++;
list = list->next;
}
if( (cnt - 1) - m < 0 ) return false;
rv = mTail;
return true;
*/
}

int main(int argc, char *argv[]) {
}



























댓글
댓글쓰기 폼
공지사항
Total
93,833
Today
0
Yesterday
12
«   2019/07   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함