4 분 소요


단순 연결리스트

  • 데이터 삽입, 삭제가 유연하게 이루어지고 크기가 정해져 있지 않다.
  • 구현은 노드를 이용하고 노드끼리 연결을 시켜 구현 한 것이다.
  • 노드에는 데이터를 저장할 변수와 다음 노드와 연결 시켜주는 변수가 존재한다.
// 예제 코드
struct Node
{
    int Data;
    Node* Next;
}


노드 생성

노드를 동적 할당하여 생성하고 그 노드를 반환해준다.

// 예제 코드
void LinkedList::Push(T data) 
{
	Node* tmp = CreateNode(data);
	if (Empty())
	{
		head = tmp;
		tail = head;
	}
	else
	{
		tail->Next = tmp;
		tail = tmp;
	}

	size++;
}


노드 탐색

연결 리스트는 배열과 다르게 인덱스로 바로 접근하지 못하고 순차 탐색을 진행해야 한다.

// 예제 코드
LinkedList::Node* LinkedList::GetNode(int idx)
{
	Node* current = head;
	int count = 0;

	while (count < idx)
	{
		current = current->Next;
		count += 1;
	}

	return current;
}


노드 삽입

새로운 노드를 헤드일 경우의 삽입과 중간 위치의 삽입을 구분한다.

// 예제 코드
void LinkedList::Insert(int index, T data)
{
    int count = 0;
    Node* current = head;
    Node* newNode = CreateNode(data);

    Node* currentParent = NULL;
    // 헤드일 경우
    if (index == 0)
    {
        // 새로운 노드를 head 노드에 연결시켜준다.
        newNode->Next = current;
        // 헤드 노드에 새로운 노드로 넘겨준다.
        head = newNode;
        size++;
        return;
    }

    // 중간일 경우
    while (count < index)
    {
	    currentParent = current; // index의 바로 앞 노드
	    current = current->Next; // index에 위치한 노드
	    count++;
    }

    currentParent->Next = newNode;
    newNode->Next = current;
    size++;
}


노드 삭제

삭제노드가 헤드일 때, 테일일 때, 중간에 위치해 있을 때를 구분한다.

void Remove(int index)
{
    Node* remove = GetNode(index);

    // 헤드를 삭제해야하기 떄문에 헤드를 다음으로 넘겨준다.
    if (head == remove)
    {
        head = head->Next;
        delete remove;
    }
    else
    {
        if (tail == remove)
        {
            Node* cur = head;

            // 테일 노드의 전까지 탐색 노드를 이동시킨다.
            while (cur->Next != tail) // tail 바로 전에 멈춤
            {
                cur = cur->Next;
            }
            
            // 테일 노드를 테일 노드의 전 노드로 넘겨주기
            tail = cur;
            tail->Next = NULL;
            delete remove;
        }
        else
        {
            Node* cur = head;

            // 삭제 노드 전까지 탐색 노드를 이동시키기
            while (cur->Next != remove) // 삭제 노드 바로 전에 멈춤
            {
                cur = cur->Next;
            }

            //삭제 노드 전의 연결을 삭제 노드의 다음 노드에 연결시킨다.
            cur->Next = remove->Next;
            delete remove;
        }
    }

    size--;
}



이중 연결리스트

  • 단순 연결 리스트와 다르게 자신의 앞 노드를 연결시켜주는 변수가 존재한다.
  • 자신의 뒤 노드와도 연결 되어 있기에 양방향 탐색이 가능해진다.

노드 추가

단순 연결리스트와 차이점은 양방향으로 연결시켜주는 과정이 필요하다.

void Push(T data)
{
    Node* newNode = CreateNode(data);

    if(Empty())
    {
        head = newNode;
        tail = head;
    }
    else
    {
        // 현재 테일이 가르키고 있는 노드의 다음 노드로 연결한다.
        tail->Next = newNode;
        // 새로 추가한 노드의 앞 노드를 현재 테일이 가르키고 있는 노드로 한다.
        newNode->Prev = tail;
        // 새로 추가한 노드를 테일 노드로 가르킨다.
        tail = newNode;
    }

    size++;
}


노드 삽입

마찬가지로 양방향으로 연결시켜주는 과정이 필요하다.

void Insert(int index, T data)
{
    Node* current = GetNode(index);
    Node* nNode = CreateNode(data);

    if (current == head) 
    {
        nNode->Next = head;
        head->Prev = nNode;
        head = nNode;
    }
    else 
    {
        current->Prev->Next = nNode;
        nNode->Prev = current->Prev;
        nNode->Next = current;
        current->Prev = nNode;
    }

    size++;
}


노드 삭제

삭제노드가 헤드일 때, 테일일 때, 중간에 위치해 있을 때를 구분한다.

void Remove(int index)
{
    Node* remove = GetNode(index);

    if (head == remove) 
    {
        head = head->Next;
        head->Prev = NULL;
        delete remove;
    }
    else 
    {
        if (remove == tail)
        {
            tail = tail->Prev;
            tail->Next = NULL;

            delete remove;
        }
        else
        {
            remove->Prev->Next = remove->Next;
            remove->Next->Prev = remove->Prev;

            delete remove;
        }
    }

    size--;
}

STL

list

  • 시퀀스 컨테이너의 일종으로 순서를 유지하는 구조이다.

  • 이중 연결 리스트로 구현되어 있다.

  • 노드 기반 컨테이너이다.

  • 원소를 접근할때 [],at 접근이 불가능하다

  • 반복자(iterator)를 사용해 데이터에 접근, 조작이 가능하다.

  • 사용하려면 헤더파일을 include 시켜야한다.

  • 삽입과 삭제가 자주 발생하는 경우에 사용하는 것이 적합하다.
  • 요소에 접근하거나 탐색이 자주 발생하는 경우에는 적합하지 않다.


생성자 종류와 선언

list<int> li;
list<float> li2(10);
list<char> li3(10, 'a');
list<char> li4(li3);
list<char> li5(li4.begin(), li4.end());

li.push_back(3);
li.push_back(4);
li.push_back(6);
li.emplace_back(5);

// 비주얼 어시스턴스
for (auto it : li) // 편리하기 한데 확실할 때만 사용
{
    cout << it << endl;
}

for (list<int>::iterator iter = li.begin(); iter != li.end(); iter++)
{
    cout << *iter << endl;
}

//결과값
3
4
6
5
3
4
6
5


맴버 함수 모음



vector

  • 시퀀스 컨테이너의 일종으로 배열과 비슷하고 동적 배열 기반의 컨테이너이며 크기가 자동으로 조정된다.

  • Random Access Iterator를 지원하는 배열기반 컨테이너이다. 그렇기에 배열처럼 [] 인덱스 연산을 통해 데이터에 접근이 가능하다.

  • 요소들은 메모리에 연속적으로 저장되기에 메모리 중간에 삽입,삭제가 일어나게되면 그 위치부터 모든 배열을 뒤로 미루거나 앞으로 당겨서 메모리를 재할당하는 문제가 생긴다.

  • 사용하려면 < vector > 헤더파일을 include 시켜야한다.

  • 리스트와 다르게 인덱스 연산이 가능하기에 요소에 대한 접근이 자주 일어나는 경우에 효율적이다.


생성자 종류와 선언

vector<int> v;
vector<float> v1(10);
vector<char> v2(10, 'a');
vector<char> v3(v2);
vector<char> v4(v3.begin(), v3.end());
vector<char> v4(v3.begin() + 5, v3.end() - 4); // 이런 식으로도 접근 가능

// 예시 코드
vector<int> v1;
v1.reserve(10); // 공간 만들어 줌

v1.emplace_back(3);
v1.emplace_back(4);
v1.emplace_back(6);

cout << v1[0] << endl;
cout << v1.capacity() << endl; // 다시 크기 줄여줌
cout << v1.size() << endl;

for (int i = 0; i < v1.size(); i++)
{
    cout << v1[i] << endl;
}

// 결과값
3
10
3
3
4
6


맴버 함수 모음

댓글남기기

참고