JAVA - LinkedList란? 그리고 구현

JAVA - LinkedList란? 그리고 구현

728x90

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 toString(ListNode head) { if (head == null) return null; List 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 } }

728x90

from http://kdg-is.tistory.com/230 by ccl(A) rewrite - 2021-12-30 02:27:24