LinkedList 구현해보기

LinkedList

• LinkedList에 대해 공부하세요.
• 정수를 저장하는 ListNode 클래스를 구현하세요.
• ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현하세요.
• ListNode remove(ListNode head, int positionToRemove)를 구현하세요.
• boolean contains(ListNode head, ListNode nodeTocheck)를 구현하세요.

---

LinkedList란 배열과 비슷하게 데이터들의 묶음을 표현할 때 사용할 수 있다. 배열은 연속적인 공간에 데이터를 저장하고 이들의 위치를 통해 (포인터) 데이터에 접근하는 반면, LinkedList는 노드 안에 데이터와 다음 노드를 가리키는 주소 값을 가지고 있어서 다음 노드를 탐색할 수 있는 방식으로 되어있다. 각 노드가 링크를 사용하
여 연결되어 있는 자료구조이다. List계열의 자료구조는 순서를 가지고 있다.

장점

• 미리 메모리를 할당하지 않아도 된다.
• 메모리의 크기를 줄이고 늘리는 작업을 하지 않아 데이터 삽입과 삭제시 O(1) 시간이 걸린다.단점
• 순서를 가지고 있기 때문에 임의 접근(Random Access)가 불가능하여 데이터 검색하는데 O(n) 시간이 걸린다.

단점

• 순서를 가지고 있기 때문에 임의 접근(Random Access)가 불가능하여 데이터 검색하는데 O(n) 시간이 걸린다.

데이터 삽입

순서가 있는 LinkedList에서 임의의 위치에 데이터를 새로 삽입하는 과정은 아래 그림과 같은 과정을 거쳐야 한다.

새로운 노드에 새로운 데이터와 삽입하고자 하는 주소 값을 복사한다.

기존 노드가 가리키는 주소 값을 새로운 노드의 주소 값으로 변경한다.

데이터 삭제

삭제 대상이 가리키고 있는 주소 값을 그 전 노드가 가리키게 한다. 삭제 대상 노드가 null을 참조하게 되면 삭제가 완료된다.

종류

노드를 어떻게 구성하느냐에 따라 여러가지 형태로 만들 수 있다.

• 단순 연결 리스트
  가장 기본적인 형태로 노드에서 다음 노드의 위치만 저장하는 형태
• 원형 연결 리스트
  마지막 노드가 맨 처음 노드를 가리키는 형태
• 이중 연결 리스트
  하나의 노드에 다음 노드의 주소값과 이전 노드의 주소값을 모두 저장하는 형태

구현

public class ListNode {  

    private int data;  
    private ListNode next;  

    public ListNode() {  
    }  
    public ListNode(int data) {  
        this.data = data;  
    }  

    private void setNext(ListNode next) {  
        this.next = next;  
    }  

    public ListNode add(ListNode nodeToAdd) {  
        ListNode lastNode = this;  
        while (lastNode.next != null) {  
            lastNode = lastNode.next;  
        }  
        lastNode.setNext(nodeToAdd);  
        return this;  
    }  

    public ListNode add(ListNode head, ListNode nodeToAdd, int position) {  
        ListNode beforeNode = head;  
        for (int i = 0 ; i < position; i++) {  
            beforeNode = beforeNode.next;  
        }  
        if (beforeNode.next != null) {  
            nodeToAdd.setNext(beforeNode.next);  
        }  
        beforeNode.setNext(nodeToAdd);  
        return this;  
    }  

    public ListNode remove(ListNode head, int positionToRemove) {  
        ListNode beforeNode = head;  
        for (int i = 0; i < positionToRemove - 1; i++) {  
            beforeNode = beforeNode.next;  
        }  

        ListNode deleteNode = beforeNode.next;  
        if (deleteNode.next != null) {  
            beforeNode.setNext(deleteNode.next);  
            deleteNode.setNext(null);  
        }  
        return deleteNode;  
    }  

    /**  
    * 값이 아니라 노드 자체를 비교  
    */  
    public boolean contains(ListNode head, ListNode nodeTocheck) {  
        ListNode checkNode = head;  
        do {  
            if (checkNode == nodeTocheck) {  
                return true;  
            }  
            checkNode = checkNode.next;  
        } while (checkNode != null);  
        return false;  
    }  

    public void print() {  
        ListNode lastNode = this;  
        do {  
            System.out.println(lastNode.data);  
            lastNode = lastNode.next;  
        } while (lastNode != null);  
    }  
}

테스트

class ListNodeTest {  

  @Test  
 @DisplayName("추가")  
  void add() {  
  ListNode list = new ListNode(10);  

  list.add(new ListNode(20));  
  list.add(new ListNode(30));  
  list.add(new ListNode(40));  
  list.add(new ListNode(50));  

  list.print();  
  }  

  @Test  
 @DisplayName("삽입")  
  void insert() {  
  ListNode list = new ListNode(10);  

  list.add(new ListNode(20));  
  list.add(new ListNode(30));  
  list.add(list, new ListNode(40), 2);  
  list.add(list, new ListNode(50), 2);  

  list.print();  
  }  

  @Test  
 @DisplayName("제거")  
  void remove() {  
  ListNode list = new ListNode(10);  

  list.add(new ListNode(20));  
  list.add(new ListNode(30));  
  list.add(new ListNode(40));  
  list.add(new ListNode(50));  

  list.remove(list, 2);  

  list.print();  
  }  

  @Test  
 @DisplayName("포함")  
  void contains() {  
  ListNode list = new ListNode(10);  
  ListNode checkNode = new ListNode(50);  
  list.add(new ListNode(20));  
  list.add(new ListNode(30));  
  list.add(new ListNode(40));  
  list.add(list, checkNode, 3);  

  assertTrue(list.contains(list, checkNode));  
  assertFalse(list.contains(list, new ListNode(50)));  
  }  

}

참고
https://github.com/jongnan/Java_Study_With_Whiteship/blob/master/week4/week4_2.md
https://blog.naver.com/hsm622/222159930944