JAVA - LinkedList란? 그리고 구현

LinkedList란?

• 각 노드가 서로 연결되어 있는 방식으로 데이터가 저장되어 있는 추상적인 자료형입니다.
• 각 노드는 데이터 필드와 다음 노드에 대한 참조로 구성되어 있습니다.
• 마지막 노드의 포인터는 NULL 값을 가집니다.

배열이 아닌 연결 리스트를 사용하는 이유

• 배열은 크기가 고정되어 있으므로 미리 배열의 크기를 할당받아야 합니다.
• 새로운 요소를 삽입하는 것에 대하여 비용이 많이 듭니다.
  • 공간을 만들고 기존 요소들을 재배치 해야합니다.

LinkedList 장점

• 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며, 일반적으로 떨어진 위치에 존재하고 해당 위치를 이전 노드가 참조하고 있습니다.
• 메모리 관리가 용이합니다.
  • 데이터가 삽입될때 마다 동적으로 할당하여 새로운 메모리 주소에 값을 할당하고 이전 노드와 연결해줍니다.
• 각 노드의 삭제와 삽입이 용이합니다.

LinkedList 단점

• 각 노드들이 흩어져 저장되므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있습니다.
  • 이를 순차 접근 또는 시퀀셜 액세스라고 합니다.
  • 임의적으로 접근할 수 없습니다.
• 접근 속도가 느립니다.
• 중간 노드가 끊어지면 그 다음 노드를 찾기가 힘듭니다.
• 연결을 위한 링크(포인터)부분이 필요하기 때문에 배열에 비해 기억공간 이용 효율이 좋지 않습니다.

LinkedList 구현 코드

public class ListNode {
    int data;
    ListNode next;

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

    public int getData() {
        return data;
    }
}

 

public class LinkedList {
    int size;

    public LinkedList() {
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    ListNode add(ListNode head, ListNode nodeToAdd, int position){
        ListNode node = head;

        // 아직 연결된 노드가 없는 경우
        // 다음 노드가 첫번째 노드가 됩니다.
        if(head == null) {
            return nodeToAdd;
        }

        // 맨 앞에 삽입하는 경우
        // 기존 노드들을 다음 노드 위치에 자리를 놓아줍니다.
        if(position == 0){
            nodeToAdd.next = head;
            return nodeToAdd;
        }

	// 순차탐색을 하여 뒤에 붙여주는 형식
        for (int i = 0; i < position -1; i++) {
            node = node.next;
        }

        // 삽입하려는 노드 (nodeToAdd)에 기존의 linkedList에서 position에 위치했던 node를 연결시킵니다.
        nodeToAdd.next = node.next;

        // 삽입하려는 위치의 바로 이전 노드에 삽입하려는 노드를 연결시킵니다.
        node.next = nodeToAdd;

        size++;
        return head;
    }

    ListNode remove(ListNode head, int positionToRemove){
        if(size <= positionToRemove || head == null){
            return null;
        }
        
        // 삭제 노드가 헤드인 경우
        // 1번 인덱스 노드를 헤드로 지정
        if(positionToRemove == 0) {
            head = head.next;
        } else {
            // 제거하려는 노드의 바로 이전 노드를 가져옵니다.
            ListNode node = head;
            for (int i = 0; i < positionToRemove - 1; i++) {
                node = node.next;
            }
            node.next = node.next.next;
        }
        size--;
        return head;
    }

    boolean contains(ListNode head, ListNode nodeTocheck){
      while (head != null) {
          if(head.getData() == nodeTocheck.getData()){
              return true;
          }
          head = head.next;
      }

      return false;
    }

    public List<Integer> toString(ListNode head) {
        if (head == null) return null;

        List<Integer> nodes = new ArrayList<>();

        while (head != null) {
            nodes.add(head.getData());
            head = head.next;
        }
        return nodes;
    }
}

 

public class Example {
    public static void main(String[] args) {

        ListNode head = null;
        LinkedList linkedList = new LinkedList();

        /**
         *  head-0
         */
        head = linkedList.add(head, new ListNode(0), 0);

        /**
         *  노드 순서대로 삽입
         *  head-1-2-3-4-Null
         *  >> head-1-2-10-3-4-Null
         */
        System.out.println("-----순서대로 삽입------");
        for(int i = 1; i <= 4; i++){
            head = linkedList.add(head, new ListNode(i),i);
        }
        System.out.println(linkedList.toString(head));

        /**
         *  노드 중간 삽입
         *  head-1-2-3-4-Null
         *  >> head-1-10-2-3-4-Null
         */
        System.out.println("-----중간 삽입------");
        head = linkedList.add(head, new ListNode(10),2);
        System.out.println(linkedList.toString(head));

        /**
         *  노드 삭제
         *  head-1-10-2-3-4-Null
         *  >> head-1-10-3-4-Null
         */
        System.out.println("-----노드 삭제------");
        head = linkedList.remove(head, 3);
        System.out.println(linkedList.toString(head));

        /**
         * 노드 포함여부 확인
         * head-1-10-3-4-Null
         */
        System.out.println("5 포함여부 :"+ linkedList.contains(head, new ListNode(5))); // false
        System.out.println("10 포함여부 :" + linkedList.contains(head, new ListNode(10))); // true

    }
}