프로그래밍, 프로그래머는 아름다워.

LinkedList

반응형
반응형

링크드 리스트는 마치 서로 연결되었다는 느낌을 주는 자료구조입니다.

node

링크드 리스트는 다음과 같이 그릴 수 있습니다.
특이하게 값뿐만 아니라 다음이 어떤 값인지 알고 있습니다. 단순히 나열하는 ArrayList와 비슷하면서 다른 느낌을 줍니다.

위 그림은 링크드 리스트에 node가 한개일때를 보여줍니다. 그렇다면 3~4개로 늘어나게 되면 어떻게 될까요?

이런식으로 그릴 수 있습니다.

생성

하얀선을 통해 다음값의 값을 알아내는 느낌입니다. 이제 구현해 봅시다.
처음에는 노드는 한개라고 생각해봅시다.

public class LinkedList {

    private Node head;
    private Node tail;
    private int size;
    private class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // 만약에, 노드를 맨처음에 넣는다면?
    public void addOne(int value) {
        Node node = new Node(value); // node에 value를 넣는다.
        head = node;
        tail = node;
        size = size + 1;
    }

}

그러면 코드는 이렇게 작성이 될 것 입니다. 노드가 하나 밖에 없으니 다음 값도 없을 뿐더러..
이 노드는 머리이자 꼬리가 될 것입니다.

add(추가)

그런데 노드를 한 개더 추가 하게 되면 어떻게 될까요?

추가하는 방법에는 2가지가 있다고 생각해봅시다. 
이로서 노드는 2개가 되었습니다.

먼저 앞에 추가하는 방법입니다.

앞에 추가하게 되면 자연스럽게 기존에 있던 노드는 뒤로 가게 됩니다.
기존에 헤드에 있던 노드는 뒤로 가게 되서 더 이상 헤드가 아니게 됩니다. 

    public void addFirst(int value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        size = size + 1;
    }

코드는 위와 같이 작성됩니다. 노드가 생성되고 기존에 있던 헤드값이 node의 다음값으로 넘어가는 느낌입니다. 
이상합니다. 마지막 노드가 보이지 않습니다. 

마지막 노드의 특징은 다음이 없습니다. 즉,꼬리라는 뜻입니다. 따라서 tail을 따로 출력해주면 됩니다.

두 번째, 뒤에 추가하는 방법입니다. 

   간단하게 생각하면 

public void addLast(int value) {
        Node node = new Node(value);
        tail = node;
        size = size + 1;
    }

코드가 이걸로 끝인것 같지만... 곰곰히 생각해보면, 아닙니다.

기존 tail의 다음값에는 어떤 값이 저장이 될까요?
바로 node값이 저장됩니다.

 public void addLast(int value) {
        Node node = new Node(value);
        tail.next = node;
        tail = node;
        size = size + 1;
    }

자 이렇게 양쪽에서 더하는 방법을 알아봤습니다.
그런데... 곰곰히 생각해보면 양쪽에서만 추가되는게 아닙니다.

중앙에서도 노드를 추가가 가능해야 합니다.

여기에서는 head와 tail이 고정되었기 때문에 굳이 조작할 필요는 없습니다.
그림을 그려보면 다음과 같습니다.

 그림을 보면 기존에 있는 의존관계는 제거 되어 있습니다.

또, 새로운 의존관계가 생겼다는 것을 확인 할 수 있습니다.
간단하게 그 값을 알기 위해

public Node getNode(int position) {
        Node cur = head;
        for(int i = 0;i<position;i++) {
            cur = cur.next;
        }
        return cur;
    }

다음코드를 사용하였다. 이제 해당 position으로 사용될 node가 무엇인지 알 수 있다.

이제 기존 의존 관계를 끝어야 한다.

즉 cur.next 는 null로 만들어줘야 한다.
그래야 연결할 수 있기 때문이다. cur.next가 null이기때문에 새로 만든 node로 연결 할 준비가 끝났다.

cur.next = new Node(value);

근데 곰곰히 생각해보면 굳이 null로 초기할 필요 없이 이것을 바로 넣어도 되지 않을까? 

다음은 두 번째 흰선을 만들어줘야한다.

public void addMiddle(int value, int position) {
        Node prev = findNode(position);
        Node tmp = prev.next;
        Node node = new Node(value);
        prev.next = node;
        node.next = tmp;
        size = size + 1;
    }

지금까지 add를 만드는 방법에 대해 알아보았다. 그런데 곰곰히 생각해보자.
이게 과연 맞는 코드일까?

Add(에러 수정)

제일 먼저 addFirst를 살펴보자.
addFirst는 가장 맨 앞에 추가된다는 특징을 가지고 있다. 만약, 맨 처음 만든다면 어떻게 될까?

null

이것을 어떻게 하면 해결 할 수 있을까?

head값은 존재하지만, tail값은 존재하지 않는다. 왜냐하면 추가하지 않았기 때문이다.

이 코드를 추가하면 된다.

if (tail == null) {
   tail = node;
}

이 코드는 마지막것이 null이라면 생성한 node를 tail로 넣어주는 코드다. 이걸 넣어주게 되면 정상적으로 동작하는것을 확인할 수 있다.

정상적으로 동작하는 것이 확인 되었다.

두 번째, 뒤에 추가할 경우 어떻게 될까?

@Test
    void addLast() {
        linkedList.addLast(3);
        assertArrayEquals(linkedList.test(),new int[]{3});
    }

test가 실패 하였다. 왜냐하면 애초에 뒤에 추가한다는건데 하나 밖에 추가 되지 않기 때문이다.

 어떻게 하면 좋을까?

처음 addLast를 하게 되면, addFirst로 바꿔주면 되지 않을까?

그래서 이렇게 추가해주었다.

if (head == null) {
    addFirst(value);
    return;
}

테스트도 성공하였다.!

다행히 정상적으로 동작한다.

@Test
    @DisplayName("addFirst addLast 섞어서")
    void addMix1() {
        linkedList.addFirst(2);
        linkedList.addFirst(3);
        linkedList.addLast(5);
        linkedList.addLast(8);
        linkedList.addFirst(1);
        assertArrayEquals(linkedList.test(),new int[]{1,3,2,5,8});
    }

이제 마지막 중앙에 추가할 경우다.
이것도 하나일때 테스트 해보자.

예상 되로 테스트에 실패 하였다.

@Test
    void middle() {
        linkedList.addMiddle(4,0);
        assertArrayEquals(linkedList.test(),new int[]{4});
    }

if (prev == null) {
    addFirst(value);
    return;
}

이것을 추가해서 테스트에 성공하였다.
하지만, position값이 1이상이면 어떻게 될까?

실패하였다. 애초에 size가 0이기 때문이다. 그러면 위치를 바꿔야 할까?

if (head == null) {
    addFirst(value);
    return;
}

이렇게 수정이 되었다. 이제는 head가 null일때는 어떤 위치에 값을 넣으려고 해도 맨 앞으로 추가 된다. 
그러면 이건 어떨까?

@Test
    void middle() {
        linkedList.addMiddle(4,2);
        linkedList.addMiddle(1,0);
        linkedList.addMiddle(2,0);
        assertArrayEquals(linkedList.test(),new int[]{2,1,4});
    }

에러다. 애초에 0을 넣는다는 의미는 맨앞에 추가한다는 의미와 같다. 그렇기 때문에 이렇게 변경하면 된다.

if (head == null || position == 0) {
    addFirst(value);
    return;
}

이제 부터 position이 0으로 설정할때는 맨 앞에 추가 되었다.

그렇다면, 이것은 어떨까?

@Test
    void middle() {
        linkedList.addMiddle(4,2);
        linkedList.addMiddle(1,0);
        linkedList.addMiddle(2,5);
        assertArrayEquals(linkedList.test(),new int[]{1,4,2});
    }

당연히 되지 않는다. 왜냐하면 5번째는 존재하지 않기 때문이다.

우리는 2가지 방법으로 이 문제를 해결 할 수 있다.
아에 안되게 만든 방법과  무조건 마지막으로 설정하는 방법이 존재한다. 어떻게 해야할까?

나 같은 경우는 마지막으로 설정하려고 한다. 

if (size - 1 < position) {
    addLast(value);
    return;
}

size-1을 한 이유는 

다음과 같은 상황 때문이다.

@Test
void middle() {
    linkedList.addMiddle(4,2);
    linkedList.addMiddle(1,0);
    linkedList.addMiddle(2,2);
    assertArrayEquals(linkedList.test(),new int[]{1,4,2});
}

왜냐하면 position : 2는 안 만들어졌기 때문이다.

이제 섞어 보자.

다행히 정상적으로 테스트는 성공하였다.

remove(제거)

remove또한 add와 마찬가지로 방법이 3가지다.

removeFirst : 

public void removeFirst() {
   Node first = head;
   head = first.next;
   size = size - 1;
}
@Test
    void removeFirst() {
        linkedList.addFirst(3);
        linkedList.addFirst(2);
        linkedList.addFirst(5);
        linkedList.removeFirst();
        assertArrayEquals(linkedList.test(), new int[]{2,3});
    }

 

removeLast :

즉, tail을 변경 시키면 된다.

public void removeLast() {
    Node prev = findNode(size-1);
    prev.next = prev.next.next;
    tail = prev;
    size = size -1;
}
@Test
    void removeLast() {
        linkedList.addFirst(3);
        linkedList.addFirst(2);
        linkedList.addFirst(5);
        linkedList.addLast(5);
        linkedList.removeLast();
        assertArrayEquals(linkedList.test(), new int[]{5,2,3});
    }

removeMiddle :

0 1 2 3 4

이렇게 되면 의존 관계가 바뀌었다.!

public void removeMiddle(int position) {
        Node prev = findNode(position);
        prev.next = prev.next.next;
        size = size -1;
}

이렇게 하면 의존성을 변경시킬 수 있다.

@Test
    void removeMiddle() {
        linkedList.addFirst(3);
        linkedList.addFirst(2);
        linkedList.addFirst(5);
        linkedList.addLast(6);
        linkedList.removeMiddle(1);
        // 5,2,3,6
        assertArrayEquals(linkedList.test(), new int[]{5,3,6});
}

 

remove(에러 수정)

공통적인 부분이 있는데, 노드가 없을 때는 어떻게 해야할까?

if (head == null) {
      throw new IllegalArgumentException("노드가 없습니다.");
}

이것을 추가했습니다.

  removeFirst 

딱히 수정할 게 없다.

removeLast

역시나 없다.

removeMiddle

0번 노드를 선택할 경우 : 

if (position == 0) {
    removeFirst();
    return;
}

나머지 :

public void removeMiddle(int position) {
        if (head == null) {
            throw new IllegalArgumentException("노드가 없습니다.");
        }

        if (position == 0) {
            removeFirst();
            return;
        }

        Node prev = findNode(position-1);
        Node tmp = prev.next.next;
        if (tmp == null) {
            tail = prev;
        }
        prev.next = tmp;
        size = size -1;
    }
@Test
    void removeMiddle2() {
        linkedList.addFirst(3); // 3
        linkedList.addFirst(4); // 2
        linkedList.addFirst(5); // 1
        linkedList.addFirst(7); // 0
        linkedList.removeMiddle(2);
        assertArrayEquals(linkedList.test(),new int[]{7,5,3});
    }

removeLast는 removeMiddle과 일치하는 부분이 발생해서  삭제하였습니다.

수정(eitd)

마지막으로 우리가 해야할 것은 수정이다. 수정도 처음,중앙,끝 3부분으로 나눈다음,
필요 없다고 느끼는 부분들은 삭제 하도록 하겠습니다.

editFirst :

간단히 head.value를 바꿔주는 선택을 했습니다.

public void editFirst(int value) {
        head.value = value;
    }
@Test
void edit() {
    linkedList.addFirst(3);
    linkedList.editFirst(5);
    assertArrayEquals(linkedList.test(),new int[]{5});
}

수정이 잘 되었다.

editLast :

public void editLast(int value) {
        tail.value = value;
}
@Test
    void editLast() {
        linkedList.addFirst(4);
        linkedList.editLast(7);
        assertArrayEquals(linkedList.test(),new int[]{7});
    }

이 역시 잘 되었다.(지금 까지는 순조롭다.)

editMiddle :

public void editMiddle(int value, int position) {
        Node cur = findNode(position);
        cur.value = value;
}
@Test
    void editMiddle() {
        linkedList.addFirst(4);
        linkedList.addFirst(3);
        linkedList.addFirst(5);
        linkedList.editMiddle(10,1);
        assertArrayEquals(linkedList.test(),new int[]{5,10,4});
    }

생각보다 수월하게 되었다.

edit(에러 처리)

이 부분은 굉장히 단순하다.

if (head == null) {
     throw new IllegalArgumentException("노드가 없습니다.");
}

 

리펙토링

전체적으로 보면서, 리펙토링해야하는 부분을 확인해 보자.

public class LinkedList {

    static final String FIND_NODE = "노드가 없습니다.";
    private Node head;
    private Node tail;
    private int size;

    private class Node {

        int value;
        Node next;

        public Node(int value) {
            this.value = value;
            this.next = null;
        }


    }

    public Node findNode(int position) {
        Node cur = head;
        for (int i = 0; i < position; i++) {
            cur = cur.next;
        }
        return cur;
    }

    public void addFirst(int value) {
        Node node = new Node(value);

        node.next = head;
        head = node;

        if (tail == null) {
            tail = node;
        }
        size = size + 1;
    }

    public void removeFirst() {
        if (head == null) {
            throw new IllegalArgumentException(FIND_NODE);
        }
        Node first = head;
        head = first.next;
        size = size - 1;
    }

    public void editFirst(int value) {
        if (head == null) {
            throw new IllegalArgumentException(FIND_NODE);
        }
        head.value = value;
    }

    public void addLast(int value) {
        Node node = new Node(value);
        if (head == null) {
            addFirst(value);
            return;
        }
        tail.next = node;
        tail = node;
        size = size + 1;
    }

    public void editLast(int value) {
        if (head == null) {
            throw new IllegalArgumentException(FIND_NODE);
        }
        tail.value = value;
    }

    public void addMiddle(int value, int position) {
        if (head == null || position == 0) {
            addFirst(value);
            return;
        }

        if (size - 1 < position) {
            addLast(value);
            return;
        }
        Node prev = findNode(position - 1);

        Node tmp = prev.next;
        Node node = new Node(value);
        prev.next = node;
        node.next = tmp;
        size = size + 1;
    }


    public void removeMiddle(int position) {
        if (head == null) {
            throw new IllegalArgumentException(FIND_NODE);
        }

        if (position == 0) {
            removeFirst();
            return;
        }

        Node prev = findNode(position - 1);
        Node tmp = prev.next.next;
        if (tmp == null) {
            tail = prev;
        }
        prev.next = tmp;
        size = size - 1;
    }


    public void editMiddle(int value, int position) {
        if (head == null) {
            throw new IllegalArgumentException(FIND_NODE);
        }
        Node cur = findNode(position);
        cur.value = value;
    }

}

더 있을 것 같지만...;;;  못찾겠다.

이제 완룐데 문제가 발생했다. 
노드가 하나일때 발생한 문제인데,
그때는 head = tail이지만, tail을 제거 하지 않았다.

public void removeFirst() {
        if (head == null) {
            throw new IllegalArgumentException(FIND_NODE);
        }

        if (size == 1) {
            tail = null;
        }
        Node first = head;
        head = first.next;
        size = size - 1;
}

마지막으로 

public void removeLast() {
        removeMiddle(size-1);
    }

 

반응형
저작자표시

'알고리즘 > 코테 알고리즘 정리 노트' 카테고리의 다른 글

나머지 연산, 약수 , 최대 공약수, 소수  (0) 2021.02.18
배열 90도 회전 (코드만 존재 설명 X)  (0) 2020.10.29
숫자 회전 (4자리 한정)  (0) 2020.10.20
위상 정렬  (0) 2020.10.01
크루스칼 알고리즘  (0) 2020.10.01

'알고리즘/코테 알고리즘 정리 노트' 관련 글

더 보기

나머지 연산, 약수 , 최대 공약수, 소수

  • 2021.02.18
더 읽기

배열 90도 회전 (코드만 존재 설명 X)

  • 2020.10.29
더 읽기

숫자 회전 (4자리 한정)

  • 2020.10.20
더 읽기

위상 정렬

  • 2020.10.01
더 읽기

댓글

Copyright © 프로그래밍, 프로그래머는 아름다워. All Rights Reserved

Designed by JB FACTORY

티스토리툴바