[Data Structures] 챕터6. 연결 리스트

Node* current = first_;
while(current->next)
{
	current = current->next;
}

순차 표현 vs 연결 표현

---

Sequential Representation

• 장점 : 데이터를 묶음별로 다룰 수 있어 효율적이다.
• 단점 : 중간에 데이터를 삽입하거나 제거하면, 그 뒤의 데이터를 이동시켜야 한다.

따라서 Sequential Representation은

• 많은 데이터를 읽어들이는데 유리하다
• 데이터를 연속적인 데이터 중간에 추가하거나 제거하는데 불리하다

Linked Representation

• 장점 : 중간에 데이터를 삽입하거나 제거하는 일이 빠르다.
• 단점 : 다음 Node에 접근하기 위해 이전에 존재하는 모든 Node를 거쳐야하므로 비효율적이다.

데이터를 삽입하거나 삭제할 때 해당 노르를 제거하거나 추가한 뒤 앞뒤 노드와 연결관계를 재설정하면 된다.

 

참고

CPU에서 메모리로 데이터를 읽어들일 때 메모리 대역폭에 맞춰서 주변 데이터를 블럭 단위로 읽어와서 일단 캐쉬에 넣어둔다. 그 다음에 요청하는 데이터가 캐쉬에 들어 있다면 재빠르게 가져오고 그렇지 않다면 다시 메인 메모리에서 데이터를 또 다시 블럭 단위로 가져옵니다. 그래서 배열 같은 순차적 자료구조에서 순서대로 데이터를 읽어오는 것은 캐쉬 효과 덕분에 아주 빠르다.

 

연결 노드(Linked List)

---

• 데이터 외에 추가로 링크 포인터도 저장(더 많은 메모리가 필요하다).
• 삽입/삭제가 편리하다는 장점을 살릴 수 없는 경우에는 메모리 낭비가 된다.
• 아이템 자체의 사이즈가 아주 큰 경우에도 포인터 하나가 추가되는 것 정도는 큰 낭비라고 볼 수 없다.

 

nullptr == 0?

int* ptr_zero = 0;       // X
int* ptr_null = nullptr; // O

숫자값 0과 비어있는 포인터를 구분하자. 이를 위해 비어있는 포인터를 0으로 사용하는 건 피하자

 

주소값 얻기

Reference와 Pointer&n.next는 포인터의 주소값을 나타낸다.

struct Node
{
	int item = 0;
	Node* next = nullptr;

	friend ostream& operator<<(ostream& os, const Node& n)
	{
		cout << &n << "주소값" << endl;
		cout << n.next << "포인터(주소 값)" << endl;

		return os;
	}
};

 

연결노드 삭제

Node* current = first;
while (current)
{
    Node*temp = current->next;
    delete current;

    current = temp;
}

 

단방향 연결 리스트(Singly Linked List)

---

Linked List의 속도

값 찾기 : O(n) 모든 값을 순회해야 함.

값 넣기 : O(1) 특정 노드 앞뒤 혹은 전체의 앞뒤에 값을 넣음.

삽입과 삭제의 시간 복잡도가 배열 리스트에서는 O(n)이지만 연결 리스트에서는 O(1)

 

여러 Linked List

• Circular List : 맨 뒤와 앞이 연결된 Linked List.
  • 마지막 노드가 맨 앞을 가리키면 된다.
• Linked Stack : 연결된 스택
• Linked Queue : 연결된 큐
•  

구현하기

Node* current = first_;
while(current->next)
{
	current = current->next;
}

 

Node* current = first_;
while(current->next && current->next->next)
{
	current = current->next;
}

이 때 current->next와 current->next->next가 nullptr인 두 가지 경우의 예외를 처리해야 한다.

 

PushFront

void PushFront(T item)
{
    // 새로운 노드 만들기
    Node* newNode = new Node; // O(1)
    newNode->item = item;

    // 연결 관계 정리
    newNode->next = first_;
    first_ = newNode;
}

 

PushBack

void PushBack(T item)
{
    if (first_)
    {
        Node* current = first_;
        while (current->next)
            current = current->next;

        Node* newNode = new Node;
        newNode->item = item;
        newNode->next = nullptr;

        current->next = newNode;
    }
    else
        PushFront(item);
}

1. while반복문 조건에 current를 넣을 경우 반복문 종료 이후 current는 nullptr가 된다.
2. 이 때 current에 동적할당 받은 새 주소를 할당받아도 마지막 바로 앞 노드의 next 포인터는 여전히 nullptr를 가리킨다.

Copy Constructor

내 구현

SinglyLinkedList(const SinglyLinkedList& list)
{
    Node* current= list.first_;
    Node* newCurrent = new Node;
    first_ = newCurrent;

    while (current)
    {
        newCurrent->item = current->item;

        if (current->next)
        {
            newCurrent->next = new Node;
            newCurrent = newCurrent->next;
        }

        current = current->next;
    }
}

 

추천 구현

SinglyLinkedList(const SinglyLinkedList& list)
{
    Node* current = list.first_;

    while (current)
    {
        this->PushBack(current->item); // handle "fisrt_"
        current = current->next;
    }
}

 

Reverse

참고 : https://www.geeksforgeeks.org/reverse-a-linked-list/

void Reverse()
{
    Node* current = first_;
    Node* previous = nullptr;

    while (current)
    {
        Node* next = current->next;
        current->next = previous;

        previous = current;
        current = next;
    }

    first_ = previous;
}

 

Find

Node* Find(T item)
{
    Node* current = first_;
    while (current)
    {
        if (current->item == item)
            return current;

        current = current->next;
    }

    return nullptr;
}

 

InsertBack

void InsertBack(Node* node, T item)
{
    Node* newNode = new Node;
    newNode->item = item;
    newNode->next = node->next;
    node->next = newNode;
}

 

Remove

첫 값을 삭제하는 경우 예외처리

void Remove(Node* n)
{
    assert(first_);

    if (first_ == n)
    {
        first_ = first_->next;
        delete n;

        return;
    }

    Node* current = first_;
    while (current->next) // check next of current instead of current
    {                     // because it could be nullptr
        if (current->next == n)
        {
            current->next = n->next;
            delete n;

            break;
        }

        current = current->next;
    }
}

 

PopBack

내구현

void PopBack()
{
    if (IsEmpty())
    {
        using namespace std;
        cout << "Nothing to Pop in PopBack()" << endl;
        return;
    }

    assert(first_);
    Node* previous = nullptr;
    Node* current = first_;

    while (current->next)
    {
        previous = current;
        current = current->next;
    }

    if (previous)
    {
        delete previous->next;
        previous->next = nullptr;
    }
    else {
        delete first_;
        first_ = nullptr;
    }
}

 

추천구현

void PopBack()
{
    if (IsEmpty())
    {
        using namespace std;
        cout << "Nothing to Pop in PopBack()" << endl;
        return;
    }

    assert(first_);
    Node* current = first_;

    if (current->next)
    {
        while (current->next->next)
            current = current->next;

        delete current->next;
        current->next = nullptr;
    }
    else
    {
        delete first_;
        first_ = nullptr;
    }
}

 

Clear

void Clear()
{
    Node* current = first_;
    while (current)
    {
        Node* temp = current->next;
        delete current;

        current = temp;
    }

    first_ = nullptr;
}

void Clear()
{
    while (first_)
        PopFront();
}

 

연결 다항식 실습(희소 다항식 구현하기)

---

부모 Class에 있는 struct Name불러쓰기

template<typename T>
class SinglyLinkedList
{
public:
    struct Node
    {
        T item = T();
        Node* next = nullptr;
    };
	...
};

class LinkedPolynomial : public SinglyLinkedList<Term>
{
public:
	typedef SinglyLinkedList<Term>::Node Node;
}

 

구현하기

NewTerm

void NewTerm(float coef, int exp)
{
    if (first_ == nullptr)
    {
        first_ = new Node;
        first_->next = nullptr;
        first_->item = Term{ coef, exp };
        return;
    }

    Node* current = first_;
    Node* previous = nullptr;
    while (current)
    {
        if (exp == current->item.exp)
        {
            current->item.coef += coef;
            return;
        }
        else if (exp < current->item.exp)
        {
            Node* newNode = new Node;
            newNode->item = Term{ coef, exp };
            if (previous)
            {
                Node* temp = previous->next;
                previous->next = newNode;
                newNode->next = temp;
            }
            else
            {
                newNode->next = first_;
                first_ = newNode;
            }
            return;
        }

        previous = current;
        current = current->next;
    }

    Node* newNode = new Node;
    newNode->item = Term{ coef, exp };
    previous->next = newNode;
    newNode->next = current;
}

 

Eval

float Eval(float x)
{
    float temp = 0.0f;

    Node* current = first_;
    while (current)
    {
        temp += current->item.coef* powf(x, (float)current->item.exp);
        current = current->next;
    }

    return temp;
}

 

Add

LinkedPolynomial Add(const LinkedPolynomial& poly)
{
    LinkedPolynomial temp;

    Node* i = this->first_;
    Node* j = poly.first_;

    while (i && j)
    {
        if (i->item.exp < j->item.exp)
        {
            temp.NewTerm(i->item.coef, i->item.exp);
            i = i->next;
        }
        else if (i->item.exp > j->item.exp)
        {
            temp.NewTerm(j->item.coef, j->item.exp);
            j = j->next;
        }
        else 
        {
            float sum = i->item.coef + j->item.coef;
            if(sum)
                temp.NewTerm(sum, i->item.exp);

            i = i->next;
            j = j->next;
        }
    }

    for(;i;i=i->next)
        temp.NewTerm(i->item.coef, i->item.exp);

    for(;j;j=j->next)
        temp.NewTerm(j->item.coef, j->item.exp);

    return temp;
}

 

Print

void Print()
{
    bool is_first = true;

    Node* current = first_;
    while (current)
    {
        if (!is_first) cout << " + ";
        else is_first = false;

        cout << current->item.coef << "x^" << current->item.exp;
        current = current->next;
    }

    cout << endl;
}

 

양방향 연결리스트(Doubly Linked List)

---

 

코팅 팁

while 반복문으로 Link의 마지막 노드를 가리키기.

Node* current = first_;

if (current->right)
{
    while (current->right)
    {
        cout << current->item << " ";
        current = current->right;
    }
    cout << current->item;
}
else { // single node
    cout << current->item << " ";
}

 

while 조건문을 code block 내부로 이동한다.

while (true)
{
    cout << current->item << " ";
    if (!current->right)
        break;

    current = current->right;
}

 

구현하기

void Reverse()
{
    Node* current = first_;

    while (current)
    {
        Node* temp = current->right; // what if current->right is nullptr?
        current->right = current->left; // you assign a value on nullptr?
        current->left = temp;
        first_ = current;	// Trick for Simplifing Code 

        current = temp;
    }
}