티스토리 뷰
Linked List(연결 리스트) - Stack / Head&Tail pointer / removeHead_bug / findMToLastElement /
DevES 2015. 11. 12. 11:06연결리스트는 동적인 데이터를 처리하는 것과 관련된 수많은 문제의 근간을 이루는 자료 구조이다.
연결리스트의 종류
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- 기초연산
- 머리 원소 추적
- 리스트 종주
- 원소의 삽입 및 삭제
스택 구현법
- LIFO: Last-In-First-Out 자료구조이다.
- 원소를 삽입하고 삭제하는 연산은 보통 각각 push와 pop이라고 부른다.
- 스택을 여러 개의 sub task로 나뉘는 task를 관리하는 데 유용하게 쓰이는 자료구조
- 스택을 사용하는 대표적인 예로 서브루틴에서 사용할 반환 주소, 매개 변수, 지역 변수 등을 추적하는 것을 들 수 있다.
- 또 다른 예로는 프로그래밍 언어를 파싱할 때 토큰을 추적하는 것을 들 수 있다.
- 배열 원소에 대한 임의의 접근이 가능함(인덱스만 알면 어떤 원소든 즉시 액세스 가능)
- 새로운 원소 할당
- 메모리 할당 과정에서 문제가 없었는지 확인
- 새로운 원소의 데이터를 설정
- 스택 맨 위에 놓은 다음 스택 포인터를 조정
- 스택이 비어있진 않은지 확인
- 맨 위에 있는 원소의 데이터를 가져옴
- 스택 포인터 변경
- 더 이상 스택에 들어있지 않은 원소의 메모리 할당을 해제
- 스택을 값으로 반환할 수 없기 때문에 스택에 대한 포인터의 포인터를 인자로 받아와야 한다.
- 스택을 값으로 반환할 수 없기 때문에 스택에 대한 포인터의 포인터를 인자로 받아와야 한다.
- pop함수를 반복적으로 호출해도 되겠지만, 연결 리스트를 종주하면서 각각을 쭉 비워줘도 된다.
- createStack과 deleteStasck 연산은 각각 생성자와 파괴자에서 처리한다.
- push와 pop루틴은 스택 객체와 연관되어서 작동할 것이기에 스택을 인자로 전달하지 않아도되고, 포인터에 대한 포인터를 넘긴다거나 하지 않아도 된다.
- 메모리 할당이 제대로 안되면 예외 상황을 던지면 된다.
/* stack_implementation.cpp */
/* 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[]) {
}
연결 리스트의 꼬리 포인터
- 일반 케이스: 리스트 중간에서 원소를 삽입/삭제하는 경우
- 특별 케이스: 맨 앞 또는 맨 뒤에서 원소를 삽입/삭제하는 경우
- 특별 케이스: 리스트의 길이에 따라(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의 버그
- 데이터가 함수에 제대로 들어오는 지 확인한다. : 없는 변수를 쓰려고 한다고나, 타입이 잘못되었거나, 작업을 수행하는데 필요한 모든 값들이 준비되어있는지 확인
- 함수의 각 줄이 제대로 작동하는지 확인한다. : 의도된 결과가 만들어지는지 확인
- 함수에서 데이터가 올바르게 나오는지 확인한다. : 예상되는 결과가 반환 값으로 돌아가야 한다. 그리고 함수를 호출한 쪽의 변수를 갱신해야 한다면 그 작업이 제대로 이뤄지는지도 확인하자.
- 흔히 발생하는 오류 조건을 확인한다. : 오류 조건은 문제에서 주어진 요구사항에 따라 다양하게 달라질 수 있다. 오류는 주로 특이한 인자 값과 연관되어 발생한다. 예를 들어, 자료 구조에 대한 연산을 수행하는 함수의 경우에는 비어있는, 또는 거의 비어있는 자료 구조를 다룰 때 문제가 생기는 경우가 많다. 포인터를 인자로 받아들이는 함수의 경우에는 NULL 포인터가 들어왔을 때 제대로 작동하지 않을 수 있다.
연결 리스트의 마지막에서 m번째 원소
- 뒤에서 m번째 원소를 찾는 일을 자주 해야하는 경우라면 단일 연결 리스트 말고 다른 자료 구조를 쓰는 것이 훨씬 나을 것이라는 의견을 피력하고 싶을 수도 있다. 실제 프로그램을 구현할 때는 당연히 다른 자료 구조를 쓰는 것이 효율적인 해결책이지만, 면접 문제에서는 주어진 그대로 풀라는 주문을 할 것이다.
- 원소의 개수를 현재 알고리즘에서 따로 구해야 한다면 연결 리스트 전체를 거의 두 번 완전히 종주해야만 한다. 메모리에 제약이 있는 시스템에서는 매우 큰 리스트가(디스크에 저장된) 페이지 아웃된 가상 메모리에 들어가 있을 가능성이 매우 높다. 그런 경우에 리스트를 한 번 완전히 종주하려면 리스트를 조금씩 순서대로 스와핑해서 메모리에 올리는 작업을 하면서 디스크에 여러번 액세스해야 한다. 이런 상황에서는 똑같은 O(n) 알고리즘이라고 해도 리스트를 한 번만 종주하면 되는 것과 두 번 종주해야 하는 것 사이의 속도 차가 상당히 크다.
- 현재 원소를 머리 위치에 추가하고 꼬리에 있는 원소를 제거하는 식으로 원소의 개수가 m개인 큐를 계속 유지하면 그 큐의 마지막 원소는 언제나 현재 위치로부터 m 원소만큼 앞에 있는 원소가 되도록 만들 수 있기 때문이다.
- Total
- Today
- Yesterday
- logging facade
- log
- logback
- object
- logging
- slf4j
- NGINX
- JVM
- java
- webserver
- TaskExecutor
- good practice
- linux
- lood
- Spring
- Apache
- runtime data areas
- async
- log level
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |