자바 기초 알고리즘 - Linked List 직접 구현하기

SSAFY B형 특강을 듣다가 처음으로 알게 된 Linked LIst

 

파이썬으로도 구현이 가능하다고 하는데, 비전공자반 수업시간에서 다루지 않았던 자료구조이기도 하고,

 

JAVA를 다루는데 아직 익숙하지 않아서인지 간단해 보이면서도 구현하기가 쉽지 않아 정리를 해두려고 합니다.

 

1. Linked List 만들기

 

Linked List는 노드들로 이루어져있는데요

 

원소 하나하나가 노드로 이루어져 있는 리스트라고 생각하면 될 것 같습니다.

 

맨 앞과 맨 뒤의 노드는 은근히 쓰일 일이 많기 때문에 Linked List 자체적으로 가지고 있도록 만들어 놓습니다.

 

그리고 size나 empty를 쉽게 구현하기 위해 size 값도 멤버변수로 하나 넣어놓습니다.

public class TestLinkedList{

    public static class LinkedList{
        Node head;
        Node tail;
        int size;
        public LinkedList(){
            this.head = null;
            this.tail = null;
            this.size=0;
        }
    }
}

 

2. Node 만들기

 

어차피 노드들은 이 Linked List 안에서만 사용될 것이기 때문에 클래스 안에 Node 클래스를 추가로 만듭니다.

 

각 Node들은 data를 갖고, next라는 레퍼런스 변수를 이용하여 다음 노드를 참조합니다.

 

값이 없는 노드는 없으므로 노드는 노드를 생성할 때 생성자로 받아주고, next 값은 링크드리스트에 연결을 해주어야 하니 일단 null으로 설정해준 뒤 직접 이어줄겁니다.

public class TestLinkedList{

    public static class LinkedList{
        Node head;
        Node tail;
        int size;
        public LinkedList(){
            this.head = null;
            this.tail = null;
            this.size=0;
        }
        // 추가되는 부분
        public class Node{
            int data;
            Node next;
            public Node(int data){
                this.data = data;
                this.next = null;
            }
        }
        //Node 완성
    }
}

 

3. addFirst 만들기

맨 앞에 원소를 추가하는 메소드입니다.

 

원소를 추가할 때 해줘야할 건 총 3가지입니다.

 

 -  head값 바꾸기

일단 새로운 노드를 맨 앞에 위치시킬 것이기 때문에, head값을 바꿔주어야 합니다.

 

일단 새로 만든 노드에 기존의 head를 연결시켜놓고 head를 바꿔주면 됩니다.

 

- size증가시키기

당연합니다.

 

 - 기존의 head가 null인지 체크하기

 이제 새로운 노드가 head가 되었습니다. head.next를 체크해줍니다. 만약 head.next가 null이라면 기존에 아무 노드도 없었다는 뜻이 됩니다. 이제 첫번 째 노드가 생겼으니 null이었던 head와 tail값을 모두 지정해줍니다. head == tail == newNode인 상태겠죠.

 

public class TestLinkedList{

    public static class LinkedList{
        Node head;
        Node tail;
        int size;
        public LinkedList(){
            this.head = null;
            this.tail = null;
            this.size=0;
        }
        public class Node{
            int data;
            Node next;
            public Node(int data){
                this.data = data;
                this.next = null;
            }
        }

        public void addFrist(int data){
            // 노드를 생성하고
            Node newNode = new Node(data);
            // 기존에 있던 head에 연결을 해줍니다.
            newNode.next = head;
            // 그리고 생성한 노드가 이제부터 head가 됩니다.
            head = newNode;
            // 만약 현재 헤드의 next가 없다면 노드가 하나뿐이므로 tail값 역시 현재 노드가 됩니다.
            if(head.next == null){
                tail = head;
            }
            size++;
        }
    }
}

 

4. addLast 만들기

 

 이번엔 처음이 아닌 마지막에 Node를 추가합니다. 당연히 newNode가 tail이 되겠죠?

addFirst와 크게 다르지 않습니다.

public void addLast(int data){
            Node newNode = new Node(data);
            tail.next = newNode;
            tail = newNode;
            size++;
        }

간단하게 이렇게 짜면 될까요?

 

이렇게 짜면 되긴 합니다만, tail값이 null일 경우를 생각하지 않았습니다.

 

tail값이 null이라면 작동하지 않습니다. 그렇기 때문에 tail이 null일 경우, 즉 리스트가 비어있을 경우에 필요한 로직을 짜주어야 합니다.

 

그 로직은 이미 addFirst에서 우리가 만들어두었습니다.

 public void addLast(int data){
            Node newNode = new Node(data);
            if(size == 0){
                addFrist(data);
            }
            tail.next = newNode;
            tail = newNode;
            size++;
        }

 

5. toString으로 확인하기

 

 이제 로직이 잘 확인하는지 테스트하기 위해 toString 함수를 만듭니다.

head부터 next로 이동하면서 data값들을 출력해주면 될 것 같습니다.

 

toString 함수는 간단하게 이렇게 작성하면 될 것 같아서 작성을 해보았는데

 

이렇게 작성하니까 값이 비어있을 때 에러가 나더라구요.

 

size값을 넣어서 size가 0이면 [] 만 출력하게 해놓는게 더 좋을 것 같습니다.

 

public String toString(){
            Node start = this.head;
            String str = "[" + this.head.data;
            while(start.next != null){
                start = start.next;
                str += "," + start.data;
            }
            str +=  "]";
            return str;
        }

 public static void main(String[] args) {
        LinkedList lst = new LinkedList();
        lst.addFrist(1);
        lst.addFrist(2);
        lst.addLast(3);
        lst.addFrist(4);
        System.out.println(lst);
    }

결과가 제대로 출력이 되는 걸 볼 수 있습니다.

 

1 -> 2, 1 -> 2, 1, 3 -> 4, 2, 1, 3 

 

6. index로 접근하기

LinkedList는 인덱스로 바로 접근할 수가 없습니다. 그렇기 때문에 순차적으로 접근해서 값을 얻어내야하는데요

public Node get(int index){
            Node node = this.head;
            for(int i=0; i<index; i++){
                node = node.next;
            }
            return node;
        }

이렇게 하면 간단하게 인덱스에 해당하는 node를 얻을 수 있겠죠?

 

이렇게 LinkedList로 맨 앞과 맨뒤에 값을 추가하고, 인덱스로 접근하는 방법을 알아보았습니다. 

 

다음에는 중간에 삽입하는 방법과 삭제한느 방법을 익혀보도록 하겠습니다.