Te JAVA (2) - 자료구조 구현 (LinkedList)

1. LinkedList 구현 (ListNode, add(), remove(), contains())
2. Stack 구현 (int 배열, push(), pop())
3. Stack 구현 (ListNode, push(), pop())
4. Queue구현 (int배열, ListNode 이용)

 

---

 

1. LinkedList 구현

LinkedList 정의

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터가 저장되는 자료구조다.
• 자바에서는 포인터가 없기 때문에 다음 노드를 저장한다.
• head 노드로 맨 앞의 노드를 저장한다.
• 리스트의 사이즈를 조정하는 데 좋은 자료구조이지만, 탐색하는데 비효율적인 자료구조다.

 

• 구현 시 주의해야할 점은 head를 반환해야 한다.
  • 어떤 함수를 사용하든 head가 매개변수로 들어온다. 즉, head는 항상 알고 있어야 한다.
  • 함수 내부에서 head가 바뀔 수 있기 때문에 head를 반환하고, 이 head를 저장해야 항상 head를 알 수 있다.

 

---

 

기본 정의

• 우선적으로 ListNode의 요소를 정의하고, 생성자와 getter, setter를 정의한다.

public class ListNode {

    private ListNode next;  // 다음 노드
    private int value;  // 저장된 값

    // 생성자
    public ListNode(int value){
        this.value = value;
    }

    // setter
    public void setNext(ListNode node){
        this.next = node;
    }

    // getter
    public int getValue(){
        return this.value;
    }

    public ListNode getNext(){
        return this.next;
    }
}

 

---

 

add 메소드

• 링크들 리스트에서 중간에 노드를 삽입하기 위해서는 이전 노드가 필요하다.
• while 문을 사용해 삽입 위치의 이전 노드(cur)를 찾는다.
• cur 노드가 가리키던 다음 노드는 삽입할 노드가 가리키는 노드가 된다.
• cur 노드의 다음 노드는 삽입하는 노드가 된다.

 

• 0이하의 위치에 삽입하는 경우 맨 앞에 삽입하도록 했다.
• head가 null인 경우 맨 앞에 삽입하는 것과 동일하다.

 

• 마지막 노드로 삽입해야 하는 경우, 마지막 노드의 다음 노드를 삽입하는 노드로 저장한다.

 

    ListNode add(ListNode head, ListNode nodeToAdd, int position){

        // 위치가 0보다 작거나 같으면 or head가 존재하지 않으면 맨 앞에 삽입
        if (position <= 0 || head == null){
            nodeToAdd.setNext(head);
            head = nodeToAdd;

            return head;
        }

        // 시작점 초기화
        ListNode cur = head;
        int idx = 0;

        // 삽입하려는 위치 이전 노드를 찾음
        // cur.getNest()가 null이라면 링크드리스트의 마지막 노드
        while(idx < position - 1 && cur.getNext() != null){
            idx++;
            cur = cur.getNext();
        }

        // cur이 마지막 노드인 경우 cur의 다음 노드를 삽입하는 노드로 자징
        if (cur.getNext() == null){
            cur.setNext(nodeToAdd);
        } else{ // cur이 중간 노드인 경우 cur의 다음 노드는 삽입하는 노드가 가리키고, cur은 삽입 노드를 가리킴
            nodeToAdd.setNext(cur.getNext());
            cur.setNext(nodeToAdd);
        }

        return head;
        
        // 어떤 경우에도 head는 알고 있어야 하고, 해당 함수에서 head가 변경되었을 수 있으므로 head 리턴.
        // 즉, 함수를 호출할 때 함수의 반환 값을 저장해야함
    }

 

---

 

remove 메소드

• 링크들 리스트에서 중간에 노드를 삭제하기 위해서는 이전 노드(cur)가 필요하다.
• cur의 다음 노드의 다음노드가 cur의 다음 노드가 된다.

 

• 범위가 벗어나는 경우와 head가 null인 경우에는 연산 없이 head를 리턴한다.
• head를 삭제하는 경우 head가 가리키는 노드를 head로 반환한다.

 

• 마지막 노드로 삽입해야 하는 경우, 마지막 노드의 다음 노드를 삽입하는 노드로 저장한다.

    ListNode remove(ListNode head, int positionToRemove){

        // head가 존재하지 않거나 삭제하는 인덱스의 범위가 음수라면 head 반환
        // head가 존재하지 않는 경우의 head 반환은 null 반환과 동일
        if (head == null || positionToRemove < 0){
            return head;
        }

        // 맨 앞 노도를 제거하는 경우 head를 제거하는 경우와 같음
        // head가 가리키던 노드를 head로 반환
        if (positionToRemove == 0){
            return head.getNext();
        }

        // 시작점 초기화
        ListNode cur = head;
        int idx = 0;

        // 삭제할 위치의 이전 노드를 찾음
        while(idx < positionToRemove - 1 && cur.getNext() != null){
            cur = cur.getNext();
            idx++;
        }

        // cur의 다음 노드가 존재하는 경우 cur의 다음 노드는 다음 노드의 다음 노드
        if (cur.getNext() != null){
            cur.setNext(cur.getNext().getNext());
        }
        // cur의 다음 노드가 존재하지 않는 경우 범위가 벗어난 노드를 제거하려는 것

        return head;
    }

 

---

 

contains 메소드

• head노드 부터 마지막 노드까지 넘어가면서 현재 cur 노드의 value와 찾고자 하는 노드의 value가 존재하는지를 확인한다.

    boolean contains(ListNode head, ListNode nodeTocheck){
        ListNode cur = head;

        // 마지막 노드까지 탐색
        while(cur != null){
            // value가 같은 노드가 존재한다면 true 반환
            if (cur.getValue() == nodeTocheck.getValue()){
                return true;
            }
            cur = cur.getNext();
        }

        // 끝까지 탐색했으나 찾지 못한 경우 false 반환
        return false;
    }

여기서 든 의문점.
나는 단순히 value가 같은지만을 비교했다.
그러나 찾고자 하는 것은 value가 아닌 ListNode형인 특정 노드라면 탐색 조건으로 다음 노드를 비교해야 할까?
내가 한 것 처럼 value만 비교한다면 contains의 함수의 매개변수가 int 형이어야 하는 게 아닐까?

 

---

 

print 메소드

• 테스트에 사용되는 print 메소드다.

    void print(ListNode head){
        ListNode cur = head;

        while(cur != null){
            System.out.print(cur.getValue() + " - ");
            cur = cur.getNext();
        }
    }

 

---

 

1 - 1. LinkedList Test

add Test

    @Test
    void add() {

        LinkedList list = new LinkedList();
        ListNode head = new ListNode(10);

        head = list.add(head, new ListNode(20), -1);
        head = list.add(head, new ListNode(30), 5);
        head = list.add(head, new ListNode(40), 1);

        list.print(head);
        // 20 - 40 - 10 - 30 -

    }

 

remove Test

    @Test
    void remove() {

        LinkedList list = new LinkedList();
        ListNode head = new ListNode(10);

        head = list.add(head, new ListNode(20), -1);
        head = list.add(head, new ListNode(30), 5);
        head = list.add(head, new ListNode(40), 1);


        // 20 - 40 - 10 - 30 -

        head = list.remove(head, 2);
        head = list.remove(head, 6);
        head = list.remove(head, -1);

        list.print(head);
        // 20 - 40 - 30 -
    }

 

contains Test

    @Test
    void contains() {

        LinkedList list = new LinkedList();
        ListNode head = new ListNode(10);

        head = list.add(head, new ListNode(20), -1);
        head = list.add(head, new ListNode(30), 5);
        head = list.add(head, new ListNode(40), 1);

        System.out.println(list.contains(head, new ListNode(10)));  // True
        System.out.println(list.contains(head, new ListNode(100))); // False
    }

 

---

 

1 - 2. 반환값 없는 LinkedList

• 기존 코드의 경우 head를 반환하고 링크드리스트를 사용하는 코드에서 head를 항상 기억해야 한다는 점이 특징이다.
• head를 외부에서 기억하는 것이 아닌 LinkedLIst 클래스 내부에서 기억을 하게 하여 반환값이 없도록 코드를 짰다.
• 이 경우 head를 return 하지 않고, class 내부의 head에 저장을 했다.
• 매개변수로 주어졋던 head도 필요없어지고, retrun 값도 없어진다.

 

기본 정의

public class LinkedListHead {

    private ListNode head;

 

add 메소드

• 위의 코드에서 달라진 점은 head가 null인 경우를 별도로 처리해준다는 점이다.
• 그리고 return 대신 head에 저장한다.

void add(ListNode nodeToAdd, int position) {
        if (head == null){
            head = nodeToAdd;
            return;
        }

        // 위치가 0보다 작거나 같으면 or head가 존재하지 않으면 맨 앞에 삽입
        if (position <= 0) {
            nodeToAdd.setNext(head);
            head = nodeToAdd;

            return;
        }

        // 시작점 초기화
        ListNode cur = head;
        int idx = 0;

        // 삽입하려는 위치 이전 노드를 찾음
        // cur.getNest()가 null이라면 링크드리스트의 마지막 노드
        while (idx < position - 1 && cur.getNext() != null) {
            idx++;
            cur = cur.getNext();
        }

        // cur이 마지막 노드인 경우 cur의 다음 노드를 삽입하는 노드로 자징
        if (cur.getNext() == null) {
            cur.setNext(nodeToAdd);
        } else { // cur이 중간 노드인 경우 cur의 다음 노드는 삽입하는 노드가 가리키고, cur은 삽입 노드를 가리킴
            nodeToAdd.setNext(cur.getNext());
            cur.setNext(nodeToAdd);
        }

    }

 

add Test 메소드

    @Test
    void add() {

        LinkedListHead list = new LinkedListHead();

        list.add(new ListNode(10), 0);
        list.add(new ListNode(20), 0);
        list.add(new ListNode(30), 0);

        list.print();
        // 30 - 20 - 10 -

    }

 

---

 

2주차 실습의 2~4 내용은 이후 블로그에 존재한다.

https://abbiddo.tistory.com/96

Te JAVA (2) - 자료구조 구현 (Stack)

https://abbiddo.tistory.com/97

Te JAVA (2) - 자료구조 구현 (Queue)