[TIL] LinkedList 로 구현한 stack

linkedList란 저장된 데이터가 (해당 데이터) + ( 다음 데이터의 포인터) 로 이루어진 구조를 뜻한다. 

이 개념을 사용하여 stack을 만들어보려한다. stack은 아래와 같다. (원래 가장 맨 위에 있는 값은 top이다)

 

우선 저장되는 데이터 형태를 link라고 한다.

Link를 구성하는 클래스는 아래와 같다. 

public class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    public Link(int d1, double d2){
        data1 = d1;
        data2 = d2;
    }
    public void printLink(){
        System.out.println("{"+data1+" , "+data2+"}");
    }
}

 

연결리스트를 실제로 구현하는 LinkList class 는 아래와 같다.

1. LinkList()

: 처음 LinkList를 생성할때는 first값 ( 스택 상 가장 top에 위치한 값) 은 null이다.

 

2. isEmpty()
: first가 null일시 true를 반환한다.

 

3. insert(int d1, double d2)

: 스택 상 값을 넣는다. 

이때 기존에 존재하던 first는 현재 들어온 데이터의 nextLink가 된다. 

그리고 가장 맨 위에 있는 값이 현재 들어온 데이터로 바뀌었으므로,  이를 first로 바꿔준다. 

 

3. delete()

: 가장 위에 있는 first의 위치를 nextLink를 통해 계속 바꾸며 가장 위에있던 temp를 반환한다. (first의 위치를 스택상 가장 안쪽 데이터로 계속 이동한다.)

public class LinkList {
    private Link first;
    public LinkList(){
        first = null;
    }
    public boolean isEmpty(){
        return first == null;
    }
    public void insert(int d1, double d2){
        Link link = new Link(d1,d2);
        link.nextLink = first;
        first = link;
    }

    public Link delete(){
        Link temp = first;
        first = first.nextLink;
        return temp;
    }
    public void printList(){
        Link currentLink = first;
        System.out.print("List : ");
        while(currentLink != null){
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println(" ");
    }
}

 

위에서 정의한 class 를 사용하여 연결리스트로 구현한 스택을 확인한다.

public class LinkListTest {
    public static void main(String[] args) {
      LinkList list = new LinkList();

        list.insert(1,500);
        list.insert(2,8700);
        list.insert(3,3400);
        list.insert(4,700);
        list.insert(5,100);

        list.printList();
        while(!list.isEmpty()){
            Link deletedLink = list.delete();
            System.out.print("this deleted : ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

 

 

출력결과 : 

 

List : {5 , 100.0}
{4 , 700.0}
{3 , 3400.0}
{2 , 8700.0}
{1 , 500.0}
 
this deleted : {5 , 100.0}

this deleted : {4 , 700.0}

this deleted : {3 , 3400.0}

this deleted : {2 , 8700.0}

this deleted : {1 , 500.0}