[스터디 4주차] LinkedList

LinkedList란?

- 연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.

- 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.

- Node는 LinkedList에 객체를 추가하거나 삭제하면 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.

- 중간에 데이터를 추가하거나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기 때문에 Array에 비해 데이터의 추가나 삭제가 용이하다.  

- 인덱스가 없기 때문에 특정 요소에 접근하려면 순차 탐색이 필요하기 때문에 탐색 속도가 떨어진다. 그러므로 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고, 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다. 

 

LinkedList 사용 법

LinkedList 선언

LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.
LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능
LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

LinkedList 구현 

class ListNode {

    int data;
    ListNode next;

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

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

}

class LinkedList {

    private ListNode head;

    public LinkedList() {
        this.head = null;
    }

    ListNode add(ListNode nodeToAdd, int position) {
        if (head == null) {
            head = nodeToAdd;
        } else {
            ListNode node = head;
            for (int i = 0; i < position - 1; i++) {
                node = node.next;
            }
            nodeToAdd.next = node.next;
            node.next = nodeToAdd;
        }

        return head;
    }

    public ListNode remove(int positionToRemove) {
        if (head == null) {
            return head;
        }
        if (positionToRemove == 0) {
            head = head.next;
            return head;
        }

        ListNode node = head;
        for (int i = 0; i < positionToRemove - 1; i++) {
            if (node == null) {
                return head;
            }
            node = node.next;
        }
        node.next = node.next.next;

        return head;
    }

    boolean contains(ListNode nodeToCheck) {
        ListNode node = head;
        while (node != null) {
            if (node.data == nodeToCheck.data) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

}