6. STL : 링크드 리스트(Linked List)를 직접 구현해 보자.

List(STL)

• 목록 & 도표마냥 여러 데이터를 관리할 수 있는 추상자료형이다.
• 데이터가 연속으로 이어져있는 시퀀스이다.
• 배열을 이용하는 방법 & 포인터를 이용하는 방법 있음.
• 스택 큐는 리스트의 특수한 형태이다. (즉, 스택 & 큐도 리스트로 구현 가능.)

LIST ADT

• 속성 : 연속으로 저장된 n개의 데이터(객체) 집합.
• 기능
  • 빈 리스트 만들기
  • 리스트 없애기
  • 데이터를 리스트에 추가하기.
  • 리스트에서 데이터 삭제
  • 리스트에서 데이터 검색
  • 리스트에 저장된 데이터 개수 확인
  • 리스트가 비어있는지 검사
  • 리스트가 꽉 찼는지 검사.

class IntList
{
private:
		int m_data[50];
		int m_count;
		
public:
		IntList();
		~IntList();
		
		void insert(int pos, int item);
		void remove(int pos);
		int search(int pos);
		int getLength();
		bool isEmpty();
		bool isFull();
}

배열을 이용한 LIST

Insert

insert : 01234에서 2에 데이터를 새로 넣는다면, 4부터 5로 옮기고 3→4 / 2→3로 옮기고

2에다가 데이터를 넣는다.

 

때문에 순서가 중요하다.

 

1. 일단 예외처리(conut가 max에 다 찼는지 부터 먼저 검사.

2. 또 카운트 범위를 벗어났는지도 예외처리 검사.

3. 그게 아니라면, 반복문을 사용해서 해당 배열의 다음 위치에 기존에 위치에 있던 데이터를 옮김.(한칸뒤로)

4. 이후 해당 위치에 아이템을 추가 하고 카운트를 올림.

void Intlist::insert(int pos, int item)
{
	if(m_count == MAX)
			return;
				
	else if(pos>count+1 || pos < 0)
		return;
				
	else
	{
		for(int i = m_count -1; i>= pos; i--)
			m_data[i+1] = m_data[i];
					  
			m_data[pos] = item;
			m_count++;
	}
}

remove

• pos 뒤쪽에 있는 것을 앞쪽으로 옮기면서 DELETE(덮어씌워서 지우기)

1. 똑같이 비었는지 예외처리 검사.

2. 범위 벗어났는지 예외처리 검사.

3. 데이터를 반복문을 이용해서 덮어 씌우기후에 카운트 감소.

void Intlist::remove(int pos)
{
	if(isEmpty())
		return;
				
	else if(pos>count-1 || pos < 0)
		return;
				
	else
	{
		for(int i =pos; i<m_count; i++)
			m_data[i] = m_data[i+1];
					  
			m_count--;
	}
}

Search

배열로 위치로 찾아서 리턴.

 

1. 위치가 유효한지 먼저 검사. 비어있으면 오류값 반환.

2. 유효다면 return 문을 사용하여 해당 배열 위치의 데이터 반환.

int IntList::search(int pos)
{
	// 위치가 유효한지 확인
	if (isEmpty() || pos < 0 || pos >= m_count)
	{
		cout << "Invalid position or list is empty." << endl;
		return -1;  // 오류 값 반환
	}

	// 유효한 위치의 값 반환
	return m_data[pos];
}

LINKED LIST(포인터)

• 인덱스가 아닌 포인터를 이용함.
• 때문에 포인터로 연결된 선형 자료구조이다.
• 구성요소 : 데이터 / 데이터를 가리키는 포인터(링크)가 있음.
• 앞쪽의 데이터를 볼수가 없기에 더블 링크드 리스트가 필요함.(앞 뒤 모두 포인터를 두는 구조)

노드 구조

• 구조체로 선언을 해줘야함. / 현재 있는 데이터의 뒤쪽 데이터를 포인터가 가르켜야함.

struct Node
{
	int Data;
	node *next;
}

node *p = new node;
p->Data = 33;
p->next = new node;
p->next->Data = 22;
p->next->next = null;

//메모리 해제

delete head;
head = null;

첫번째 위치는 항상 리스트는 헤드를 기준을 시작함.(첫 데이터 위치)

→ 포인터 변수임.(주소가 들어감.) 첫번째 노드의 주소.

→ 제일 마지막 부분은 항상 NULL임.

항상 데이터를 중간에 있는걸 찾을 때마다 배열과 다르게 포인터 맨 첫부분(0번)부터 탐색해야함. (배열은 중간에 해도 상관이 없긴한데…)

그래서 검색은 배열형 리스트가 빠르고, 주입이나 삭제는 링크드 리스트(포인터)가 더 빠름.

노드 데이터 출력 방법

node* temp = head; // 노드의 헤드가 가리키는 데이터 부분을 복사.
while(temp != null) //노드 맨끝(null)이 아니라면
{
	cout <<temp ->Data; // 데이터를 출력
	temp = temp -> next; //다음 노드로 넘어감.
}

노드 인서트(주입) 방법(순서 중요)

node *p = new node;
p->Data = 8;
p->next = temp -> next;
temp->next = p;

인서트할 데이터에 next정보를 넣은 다음 그 원래 앞에 있는 데이터에 또 수정을 하는 순서로 해야함.

노드 딜리트(삭제) 방법

node *p;
p = temp ->next;
temp -> next = p-> next;
delete p;

링크드 리스트 완성 :)

#include <iostream>
using namespace std;

struct node
{
    int data;
    node* next;
    node(int item) : data(item), next(nullptr) {};
};

class IntLinkedList
{
private:
    node* m_head;
    int m_count;

public:
    IntLinkedList() : m_head(nullptr), m_count(0) {}

    ~IntLinkedList() {
        while (m_head != nullptr) {
            node* temp = m_head;
            m_head = m_head->next;
            delete temp;
        }
    }

    void insert(int pos, int item) {
        if (pos < 0 || pos > m_count) {
            cout << "Invalid position" << endl;
            return;
        }

        node* newNode = new node(item);

        if (pos == 0) {
            newNode->next = m_head;
            m_head = newNode;
        }
        else {
            node* current = m_head;
            for (int i = 0; i < pos - 1; i++) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }

        m_count++;
    }

    void remove(int pos) {
        if (pos < 0 || pos >= m_count) {
            cout << "Invalid position" << endl;
            return;
        }

        node* temp;

        if (pos == 0) {
            temp = m_head;
            m_head = m_head->next;
        }
        else {
            node* current = m_head;
            for (int i = 0; i < pos - 1; i++) {
                current = current->next;
            }
            temp = current->next;
            current->next = temp->next;
        }

        delete temp;
        m_count--;
    }

    int retrieve(int pos) {
        if (pos < 0 || pos >= m_count) {
            cout << "Invalid position" << endl;
            return -1;  // 오류를 나타내는 값
        }

        node* current = m_head;
        for (int i = 0; i < pos; i++) {
            current = current->next;
        }

        return current->data;
    }

    int getLength() {
        return m_count;
    }

    bool isEmpty() {
        return m_count == 0;
    }
};

int main()
{
    IntLinkedList list;

    list.insert(0, 10);
    list.insert(1, 20);
    list.insert(2, 30);

    cout << "List length: " << list.getLength() << endl;
    cout << "Element at position 1: " << list.retrieve(1) << endl;

    list.remove(1);

    cout << "New list length: " << list.getLength() << endl;
    cout << "Is the list empty? " << (list.isEmpty() ? "Yes" : "No") << endl;

    return 0;
}

• insert: 지정된 위치에 새 노드를 삽입합니다. 리스트의 시작, 중간, 끝에 삽입할 수 있습니다.
• remove: 지정된 위치의 노드를 제거합니다. 첫 번째 노드 제거와 다른 노드 제거를 구분하여 처리합니다.
• retrieve: 지정된 위치의 데이터를 반환합니다.
• getLength: 현재 리스트의 길이(노드 수)를 반환합니다.
• isEmpty: 리스트가 비어있는지 확인합니다.