본문 바로가기
스터디/[white-ship] 자바 스터디(study hale)

4주차 과제 LinkedList

by doyoungKim 2021. 1. 2.

목차

LinkedList에 대해

  • 정수를 저장하는 ListNode 클래스를 구현
  • ListNode add(ListNode head, ListNode nodeToAdd, int position)를 구현
  • ListNode remove(ListNode head, int positionToRemove)를 구현
  • boolean contains(ListNode head, ListNode nodeTocheck)를 구현

 

LinkedList에 대해

LinkedList 는 각 노드가 데이터와 다음노드를 가르키는 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.

출처: https://github.com/jongnan/Java_Study_With_Whiteship/blob/master/week4/image/linked_list.png

​

데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.
Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.​

ArrayList와 비교해서 인덱스가 존재 하지 않아, 추가 삭제 하더라도 인덱스가 변경될 일이 없어 좀 더 용이하다.
하지만 반대로, 인덱스가 없어서 임의의 값을 찾기 위해서는 처음부터 값을 순회해서 탐색해야하는 단점이있다.

​

정리

탐색 또는 정렬을 자주 하는 경우엔 배열 사용
데이터의 추가/삭제가 많은 경우 연결 리스트

​

정수를 저장하는 ListNode 클래스를 구현

LinkedList 안에 노드 는 data 와 다음 노드를 가르키는 포인터로 구성되어 있다.

따라서 다음과 같이 클래스를 작성했다.

public class ListNode {

    // 정수 데이터
    private Integer data;

    // 다음 ListNode 좌표
    private ListNode point;

    public ListNode() {
    }

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

    public int getData() {
        return data;
    }

    public ListNode getPoint() {
        return point;
    }

    public void updateNextPoint(ListNode point) {
        this.point = point;
    }
}

​

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

LinkedList를 구현하는 것 이니까 LinkedList 라는 클래스를 따로 만들었다.

public class LinkedList {

    /**
     * 원하는 위치에 노드를 추가 하는 기능
     *
     * @param head      첫 번째 노드를 가르키는 용도의 ListNode (데이터 저장 X)
     * @param nodeToAdd 추가할 ListNode
     * @param position  추가할 위치
     * @return 추가한 ListNode
     */
    ListNode add(ListNode head, ListNode nodeToAdd, int position) {

        ListNode target = head;

        //해당 Node 를 넣어야할 position 전까지 이동.
        for (int i = 0; i < position - 1; i++) {

            // 다음 노드가 없을 경우 가장 마지막 노드를 반환
            if (target.getPoint() == null) {
                break;
            }

            target = target.getPoint();
        }

        // 추가될 노드 직전 노드
        ListNode currentNode = target;
        final ListNode nextNode = target.getPoint();

        // 기존
        // A(target) -> C(target.point)

        // 추가할 노드에 기존에 다음 노드 를 삽입
        // B(nodeToAdd) -> C(target.point)
        nodeToAdd.updateNextPoint(nextNode);

        // 기존에 다음 노드에 추가한 노드
        // A(target) -> B(target.point = nodeToAdd) -> C (nodeToAdd.point)
        currentNode.updateNextPoint(nodeToAdd);

        return head;
    }
}

​

LinkedList 에 가장 처음 부분은 항상 head 이다.
head를 통해서 노드들이 연결 연결 되는 것이고 그 연결 사이에 노드를 넣는 메소드 이다.

​노드 사이에 들어 갈때 추가될 직전 노드와 추가되는 노드의 각각 포인터를 변경하는 과정이 조금 어려웠다.

기존 노드가 다음과 같을때, B(nodeToAdd) 를 A 와 B 사이에 추가가 될때,
A(target) -> C(target.point)

A -> B -> C 
가 되도록 각각 노드의 포인터를 변경해줘야한다.

1. A 다음은 C 가 아니라 B 여야한다.
        currentNode.updateNextPoint(nodeToAdd);
2. B 다음은 이제 C 여야 한다.
        nodeToAdd.updateNextPoint(nextNode);

A(target) -> B(target.point = nodeToAdd) -> C (nodeToAdd.point)

​

 

ListNode remove(ListNode head, int positionToRemove)를 구현​

    /**
     * 원하는 위치에 노드를 삭제하는 기능
     *
     * @param head             첫 번째 노드를 가르키는 Node
     * @param positionToRemove 삭제할 ListNode 위치
     * @return 삭제한 ListNode
     */
    ListNode remove(ListNode head, int positionToRemove) {
        ListNode target = head;

        if (positionToRemove <= 0) {
            System.out.println("positionToRemove 은 양수만");
            return null;
        }


        //해당 Node 를 삭제할 position 전까지 이동.
        for (int i = 0; i < positionToRemove - 1; i++) {

            //삭제 position 이 클경우 아무런 삭제도 하지 않음.
            if (target.getPoint() == null) {
                System.out.println("기존 Node 길이 보다 큰 위치 값"); 
                return null;
            }

            target = target.getPoint();
        }


        ListNode deletePrevNode = target;
        ListNode deleteTargetNode = deletePrevNode.getPoint();
        // 제거 하려고 하는 node 가 없다면 아무런 삭제도 하지 않음
        if (deleteTargetNode == null) {
            System.out.println("제거 하려는 노드가 없음");
            return null;
        }

        ListNode deleteNextNode = deleteTargetNode.getPoint();

        deletePrevNode.updateNextPoint(deleteNextNode);


        //변경 전 :A(tempNode) -> B(positionToRemove) -> C
        //변경 후 :A(tempNode) -> C

        return head;
    }

add 메소드와 마찬가지로 제거할 Node 직전 으로 이동한다.

직전 Node 에 타겟을 그 다음 타겟으로만 변경해주면 된다.

기존 노드가 다음과 같을때, A 와 B 와 C 사이에 B가 삭제 될때
A -> B -> C 

A -> C 
가 되도록 각각 노드의 포인터를 변경해줘야한다.

1. A 다음은 B 가 아니라 C 여야한다.
        deletePrevNode.updateNextPoint(deleteNextNode);

A(target) -> C (target.point.point)

​

​

 

boolean contains(ListNode head, ListNode nodeTocheck)를 구현​

해당 노드가 포함되어 있는지 확인하는 방법은 간단하다.

head 부터 끝까지 순회하면서 같은 node 가 있는지 확인만 하면 된다.

단 주의할 점이 있다면, equals를 사용하기 때문에 ListNode 클래스에서 오버라이딩이 필요하다.

// LinkedList.class

 /**
     * 해당 노드가 포함되어 있는지 확인하는 기능
     *
     * @param head        첫 번째 노드를 가르키는 Node
     * @param nodeToCheck 확인하기 위한 노드
     * @return Boolean 존재 여부
     */
    boolean contains(ListNode head, ListNode nodeToCheck) {
        while (head != null) {
            if (head.equals(nodeToCheck)) return true;
            head = head.getPoint();
        }
        return false;
    }

    //결과값 출력함수.
    public String toString(ListNode head) {
        StringBuilder str = new StringBuilder();
        ListNode tempNode = head;

        int index = -1;
        while (tempNode != null) {

            index++;

            // head 일 경우 생략
            if (index == 0) {
                tempNode = tempNode.getPoint();
                continue;
            }

            str.append(tempNode.getData()).append(" ");

            if (tempNode.getPoint() == null) {
                break;
            }

            tempNode = tempNode.getPoint();


        }


        return str.toString();
    }

 

// ListNode
   
   ...

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || this.getClass() != o.getClass()) return false;
        ListNode other = (ListNode) o;
        return this.data == other.data && Objects.equals(this.point, other.point);
    }

​

최종적으로 데모코드로 마무리 해보겠다.

 

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        //Test 노드 작성
        ListNode headNode = new ListNode();  //head
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);

        headNode = linkedList.add(headNode, node2, 1);
        headNode = linkedList.add(headNode, node3, 2);
        headNode = linkedList.add(headNode, node4, 3);
        headNode = linkedList.add(headNode, node5, 4);
        headNode = linkedList.add(headNode, node6, 5);
        headNode = linkedList.add(headNode, node7, 6);
        headNode = linkedList.add(headNode, node8, 7);

        System.out.println(linkedList.toString(headNode));

        headNode = linkedList.remove(headNode, 7);
        headNode = linkedList.remove(headNode, 6);
        headNode = linkedList.remove(headNode, 5);
        headNode = linkedList.remove(headNode, 4);
        headNode = linkedList.remove(headNode, 3);
        headNode = linkedList.remove(headNode, 2);
        headNode = linkedList.remove(headNode, 1);

        System.out.println(linkedList.toString(headNode));

        final boolean contains = linkedList.contains(headNode, node2);
        System.out.println(contains);

    }
}
// 출력 결과
2 3 4 5 6 7 8 

false

 

 

 

출처

728x90
저작자표시

'스터디 > [white-ship] 자바 스터디(study hale)' 카테고리의 다른 글

4주차 과제: 제어문  (0) 2021.01.02
4주차 과제: live-study 대시 보드  (0) 2021.01.02
4주차 과제: Stack  (0) 2021.01.02
4주차 과제: Queue  (0) 2021.01.02
5주차 과제: 클래스  (0) 2021.01.01

관련글

댓글

티스토리툴바