Linked List( 단일연결 )

단일 연결 리스트는 아래의 그림 처럼 각 데이터 원소에는 리스트의 다음 원소에 대한 연결고리(Link)가 들어있다. 
거기서  head라는 포인터가 맨 앞을 가리키고 있다. 

 

단일 연결리스틑 객체를 생성할때 heap 영역에 들어가며 서로의 데이터는 바로 옆에 할당이 안될 수도 있다.

 

임의의 N번쨰 값을 검색 할 시
n번째의 값을 접근 시에는 head를 통해 맨 앞 노드를 접근하여 순차적으로 앞->뒤로 찾아가며 검색해야한다. 이는 O(n)이라는 시간복잡도를 갖는다. 

 

노드를 삭제 또는 생성 할 시
노드의 삭제, 생성은 가리키는 연결고리(link) 만 바꾸고 노드를 메모리에서 해지해주면 되기 때문에 굉장한 효율 갖고 있다는 장점이 있다.

그럼 C++로 코드를 만들어보겠다.  

노드코드

template <class T>
class Node{
	public:
		Node(const T &value) : next(nullptr), data(value){}
		~Node() {}
		Node* getNext() const{  return next;  }
		const T& getValue() const{  return data;  }

	public:
		T data;
		Node* next;
};

 

const로 반환하는 데이터를 상수로 리턴하여 호출 부분으로부터 변경하지 못하도록 방지하기 위해 선언했다. 

 

이제 LinkedList 함수 하나씩 만들면서 살펴보자. 

여기서 Node<T> *head 변수가 해당 클래스 안에 있다고 가정

 

 

 

1. addFrontNode 함수 : 맨 앞에 넣는 것. 

bool addFrontNode(T _value) //리스트 맨 앞에 추가하기
	{
		Node<T>* newNode = new Node<T>(_value);
		if (!newNode) return false; 

		//만약 값이 하나도 없을때
		if (head == nullptr){
			head = newNode;
			return true;
		}
		
		//값이 하나 이상 일때
		newNode->next = head;
		head = newNode;
		return true;
	 }

 

 

값이 정상적으로 할당되었다면 true를 반환해준다. 
맨 앞에 추가할떄는 2가지를 고려하면 된다.
1. 값이 하나도 없을 때
2. 값이 하나 이상 있을 때

값이 하나도 없을때는 head가 null이기 때문에 값이 들어간 후 head를 넣어준다.

 

 

 

 

2. addNode 함수 : 맨 뒤에 넣는 것.(Tail이 없다고 가정) 

bool addNode(T _value) //맨 뒤에 추가하기
	{
		Node<T>* newNode = new Node<T>(_value);
		Node<T> *temp = head;
		if (!newNode) return false;

		//만약 값이 하나도 없을때
		if (head == nullptr) {
			head = newNode;
			return true;
		}

		//값이 하나 이상 일때
		while (temp->next){
			temp = temp->next;
		}
		temp->next = newNode;
	}

값이 정상적으로 할당되었다면 true를 반환해준다. 
맨 뒤에 추가할떄는 마찬가지로 2가지를 고려하면 된다.
1. 값이 하나도 없을 때
2. 값이 하나 이상 있을 때
여기서 값이 하나 이상일때는 while 문을 통해 다음 노드가 null일때까지 반복문을 실행한다.

만약 false가 떨어졌다는 것은 null이라는 뜻은 temp의 노드가 마지막이라는 것 -> 해당 temp의 next로 값을 넣어준다.(마지막 삽입)

 

 

 

3. InsertNode : 원하는 값을 매개변수로 전달하여 해당 노드 앞에 삽입하는 함수

bool InsertNode(T _insertNextValue, T _value)
    {
        //고려사항(2가지) 
        //하나도 없을 때 
        //값이 존재 하지 않을떄
        //값이 존재할때. 
        Node<T>* newNode = new Node<T>(_value);
        Node<T>* tempNode = head;

        //값이 하나도 없을 떄 
        if (tempNode == nullptr)
            return false;

        while (tempNode->next)
        {
            if (tempNode->data == _insertNextValue)
            {
                newNode->next = tempNode->next;
                tempNode->next = newNode;
                return true;
            }
            tempNode = tempNode->next;
        }
    }

원하는 값의 노드 앞에 삽입하는 경우이다. 
여기서 고려사항은 
1. list가 하나도 없는데 삽입할려고 할때
2. 값이 1개 이상 존재할때

 

4. DeleteNode(T _value) : 원하는 데이터를 갔고 있는 노드 삭제할 때(중요)

bool deleteNode(T _value)
    {
        Node<T>* temp;
        Node<T>* preTemp;

        //값이 하나도 없을때
        if (head == nullptr)
            return false;

        temp = head->next;
        preTemp = head;

        //삭제하는 값이 머리에 있을 떄
        if (head->data == _value) {
            head = temp;
            delete preTemp;
            return true;
        }

        //길이 2 이상 && 머리가 아닌 것을 삭제할때
        while (temp->next)
        {
            if (temp->data == _value)
            {
                preTemp->next = temp->next;
                delete temp;
                return true;
            }
            preTemp = temp;
            temp = temp->next;
        }

        return false;
    }

deleteNode에서는 삭제하고 다음걸로 연결하기로 생각하면 안된다. 노드를 삭제하고 이미 존재 하지 않는 값을 next로 연결해주게 된다면 중간에 끊겨버린 리스트가 되고 말것이다. 

그러기 때문에 삭제 할 노드의 앞을 가리키는 preTemp를 추가적으로 생성하여 temp 뒤쪽을 계속 따라가도록 해야한다. 물론 temp -> next -> value로 현재 위치의 다음 노드르 value값을 불러와 비교 해줘도 되지만 그렇게 되면 삭제할려고 하는 값이 만약 head라면 이때 문제가 발생한다. 

마무리로 소멸자도 까먹지 말고 넣어주자.

5. 소멸자

    //소멸자
    ~LinkedList()
    {        
        Node<T>* deleteNode = head;
        while (deleteNode)
        {
            Node<T>* temp = deleteNode->next;
            delete deleteNode;
            deleteNode = temp;
        }
    }

 

하나씩 타도 들어가 삭제해주면 된다. 이때 중요한것은 삭제 전 꼭 다음 노드를 먼저 temp에 담아줘야 한다. 그래야 다음 노드로 넘어 갈 수 있다.

 

 

 

 

 

+)

면접질문

만약 단일 링크드 리스트에서 뒤에서 M 번째의 data 값을 가져오라고 할때 어떻게 해야 가장 최적화된 방법을 찾을 수 있을까? (length가 저장된 변수가 따로 없다고 가정)

여기서 중요한것은 "뒤에서" 이다. 링크드 리스트는 뒤로 못간다는 것. 한번 고민해보자.