링크드리스트(Linked List)

링크드리스트(Linked List)

https://en.wikipedia.org/wiki/Linked_list

배열은 원소를 삽입, 삭제할때 새로운 저장 공간을 새로 만들거나 원소를 당겨버리는 행동을 하는 등 시간복잡도가 O(n)이 걸리곤 했다. 링크드 리스트는 이 삽입, 삭제에 걸리는 시간을 줄이기 위해 탄생한 자료구조

자료를 저장할때 자료값만 저장하는 것이 아니라 다음 자료가 저장되어있는 위치를 함께 저장시키는 자료구조

저장공간의 크기는 가변적이다.

메모리 공간이 배열과는 달리 연속적으로 구성되어 있지 않다. 원소의 저장이 메모리에 연속으로 들어가는 것이 아니라 원소값과 다음 원소값이 저장되어있는 주소값이 함께 저장되어 있어 그 주소값을 찾아 원소를 탐색해 나간다. 그러므로 배열(Array)의 인덱스(Index)를 통한 접근이 불가능하다.

장점

새로운 원소를 삽입할때 시간복잡도 O(1)

https://en.wikipedia.org/wiki/Linked_list

원소를 삭제할때 시간복잡도 O(1)

https://en.wikipedia.org/wiki/Linked_list

새로운 원소가 삽입되거나 삭제될때 배열과는 달리 새로운 저장공간을 만들어줄 필요가 없음. 메모리가 조금 더 효율적

단점

원소 조회시 배열처럼 인덱스를 통해 바로 접근하는 것이 아니라 연결된 다음 주소를 타고타고 들어가며 조회해야하므로 O(n)

원소 수정 역시 조회를 먼저 한뒤 값을 변경하게 되므로 조회에 필요한 O(n)이 시간복잡도가 걸리게 된다.

Code

import java.util.NoSuchElementException; class Main { public static void main(String[] args) { MyLinkedList linkedList = new MyLinkedList<>(); linkedList.add(1); linkedList.add(2); linkedList.add(3); linkedList.add(0, 0); linkedList.add(2, 7); printElements(linkedList.size(), linkedList); linkedList.delete(0); linkedList.delete(0); linkedList.delete(0); linkedList.delete(0); printElements(linkedList.size(), linkedList); } public static void printElements(int size, MyLinkedList linkedList) { for (int i = 0; i < linkedList.size(); i++) { System.out.print(linkedList.get(i) + " "); } System.out.println(); } } class Node { E data; Node next; public Node(E data) { this.data = data; this.next = null; } } class MyLinkedList { private Node head; private Node tail; private int size; public MyLinkedList() { this.head = null; this.tail = null; this.size = 0; } // 특정 위치 노드 반환 private Node searchNode(int index) { validateIndex(index, size); Node node = head; for (int i = 0; i < index; i++) { node = node.next; } return node; } // 링크드리스트 값 추가 public void add(E value) { if (size == 0) { addFirst(value); return; } Node node = new Node(value); tail.next = node; tail = node; size++; } public void add(int index, E value) { validateIndex(index, size); if (index == 0) { addFirst(value); return; } if (index == size) { add(value); return; } // 추가하려는 위치의 이전 노드 Node prevNode = searchNode(index-1); // 추가하려는 위치의 노드 Node nextNode = prevNode.next; // 추가하려는 노드 Node newNode = new Node(value); prevNode.next = newNode; newNode.next = nextNode; size++; } private void addFirst(E value) { Node node = new Node(value); node.next = head; head = node; size++; if (head.next == null) { tail = head; } return; } public void delete(int index) { if (index == 0) { deleteFirst(); return; } validateIndex(index, size); Node prevNode = searchNode(index-1); Node targetNode = prevNode.next; Node nextNode = targetNode.next; prevNode.next = nextNode; targetNode.data = null; targetNode.next = null; size--; } private void deleteFirst() { if (head == null) { throw new NoSuchElementException(); } Node nextNode = head.next; head.data = null; head.next = null; head = nextNode; size--; if (size == 0) { tail = null; } } public E get(int index) { return searchNode(index).data; } public void set(int index, E value) { Node node = searchNode(index); node.data = value; } public int size() { return size; } private void validateIndex(int index, int size) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } } }

from http://epser.tistory.com/30 by ccl(A) rewrite - 2021-12-16 18:00:30