Linked List

이번 글에서는 Linked List를 다뤄보겠습니다.
C++ 코드는 이곳에서 확인할 수 있습니다.

이전 글에서 queue에 대해서 살펴봤는데, linked list와 차이점을 살펴보자면 다음과 같습니다. Queue는 enque/dequeue operation만을 지원하기 때문에 FIFO (First Input First Output)인 반면에, linked list는 push front/back을 지원하기 때문에 element가 먼저 삽입된 element가 반드시 먼저 list에서 제거되지 않습니다.

Linked list의 method를 그림으로 살펴보면 위와 같습니다. Linked List에서 구현해야하는 핵심적인 method 3가지를 표현했습니다. 각 method에 맞춰서 element가 head/tail을 update하도록 구현하면 됩니다. 이를 코드로 살펴보면 아래와 같습니다.

struct Node{
  Node(int d = 0, Node *l = 0): data(d), link(l){}
  int data;
  Node *link;
};

우선, list를 구성하기 위한 node를 먼저 선언했습니다. 모든 노드는 다음 node를 pointing 하는 link member variable을 포함하고 있습니다.

class IntList{
public:
  IntList(){last = first = 0;}
  bool IsEmpty(){return !first;}
  void Push_Back(int);
  int  Front();
  void Pop_Front();
  void Push_Front(int);
  void Insert(int);
private:
  Node *first;
  Node *last;
  friend ostream& operator<<(ostream&, IntList&);
};

다음으로 linked list에 대한 class입니다. Linked list에는 기본적으로 Push_Front/Back() method와 Pop_Front() method를 선언하였습니다. 또한, list의 head와 tail을 가리키는 first와 last member variable을 포함하고 있습니다.

void IntList::Push_Front(int e){
  if(!first) first = last = new Node(e);
  else{//지우고 넣기가 아니라 내버려 둔 상태에서 넣기
    first = new Node(e, first);
  }
}

각 메소드에 대한 구현은 단순합니다. list에 element를 push하고자 하는 경우, list가 empty이면 firt와 last pointer가 새로 입력되는 element를 가리키도록합니다. 반면, list가 비어있지 않은 경우, list의 first가 새로운 노드를 가리킴과 동시에 새로운 노드가 기존의 first element를 point 할 수 있도록 구현했습니다.

void IntList::Push_Back(int e){
  if(!first) first = last = new Node(e);
  else{
    last->link = new Node(e);
    last = last->link;
  }
}

Push_Back()은 Push_Front()와 정반대로 구현했습니다. Push_Front()의 first 자리에 last를 대체하고, empty가 아닌 경우만 last를 새로운 node로 대체하도록 구현했습니다.

void IntList::Pop_Front(){
  if(!first);
  first = first->link;
}

Pop_front()는 first element를 제거해주면 됩니다. Pop_front()에서 first elemnt를 리턴값으로 받고자 하면 return first;만 추가해주면 됩니다.

이상으로 linked list의 핵심적인 method와 구현을 살펴봤습니다. 내용에 질문이 있으시거나 잘못된 내용에 대한 피드백은 댓글로 남겨주시기 바랍니다.
감사합니다.