Java의 간단한 LinkedList 구현 방법

LinkedList와 ArrayList는 모두 List 인터페이스의 구체적인 실현 클래스입니다.LinkedList와 ArrayList는 기능적으로도 대체적으로 일치하지만 구체적인 실현 방식이 일치하지 않기 때문에 같은 조작을 할 때 효율도 차이가 있다.
추상적인 데이터 구조인 선형표에 대해 말하자면 선형표는 두 가지로 나뉘는데 하나는 순서 저장 구조의 순서표이고, 다른 하나는 지침을 통해 그 논리적 위치를 묘사하는 체인표이다.
구체적인 Java 구현:

순서대로 저장된 순서표는 수조로 이루어져 있으며, 수조를 바탕으로 각종 조작을 봉인하여 형성된 List는 ArrayList

체인 테이블은 포인터로 논리적 위치를 설명하고 자바에서 양방향 체인 테이블을 바탕으로 여러 가지 조작을 봉인하여 형성된 List는 LinkedList

삽입과 삭제 작업에 대해ArrayList는 하나의 요소를 삽입할 때마다 우선 수조의 공간이 충분하고 충분하지 않은지 판단해야 한다. 확장을 해야 한다. 충분한 공간이 있는 토대에서 지정한 index 위치에 요소를 삽입하지만 이 index와 이후의 요소는 모두 뒤로 옮겨야 한다.삭제 작업은 공간이 충분한지 판단할 필요가 없지만 이 index와 이후의 요소가 앞으로 이동해야 하기 때문에 이러한 이동 작업은 시간의 복잡도를 증가시킬 수 있다.그러나 LinkedList의 경우 포인터를 사용하여 논리적 위치를 표시하므로 삽입 및 삭제 작업의 시간 복잡도는 **O(1)**입니다.
ArrayList의 경우 삽입과 삭제의 시간 복잡도가 높지만 지정된 위치의 요소를 찾는 작업은 수조를 통해 이 아래 표시에 대응하는 요소를 직접 얻을 수 있기 때문에 매우 빠르다.오히려 LinkedList의 경우 지정된 위치의 요소를 직접 반환할 수 없으며 하나의 질의가 필요합니다. 그 시간의 복잡도는 **O(n)**입니다.
Java의 ArrayList 클래식 엔티티 클래스 구현 방법과 마찬가지로 실현의 목적은 주로 정부의 실현 원리와 기교를 연습하고 파악하는 데 있기 때문에 다른 유형과 협조해야 하는 방법과 기능이 많기 때문에 여기서 실현되지 않는다. 예를 들어iterator 등이다.
따라서 LinkedList를 구현하는 방법은 다음과 같습니다.
add 방법
get 방법
indexOf 방법
제거 방법
Array List를 구현하는 이름과 마찬가지로 Simple Linked List입니다.소스 주소, 환영스타,fork
양방향 체인 테이블 구축
구축된 코드는 다음과 같습니다.

 private static class Node<E>{
 E item;
 Node<E> next;
 Node<E> prev;
 public Node(E item, Node<E> next, Node<E> prev) {
 this.item = item;
 this.next = next;
 this.prev = prev;
 }
 } 

일반적인 양방향 체인 테이블의 구축 방법, 하나의 디지털 영역 저장 그룹, 하나의 앞쪽 바늘은 하나의 Node 유형의 요소를 가리키고, 뒷쪽 바늘은 하나의 Node 유형의 요소를 가리킨다.
LinkedList 구현에는 다음 세 개의 구성원 변수가 필요합니다.

 private int size;
 private Node<E> first;
 private Node<E> last;

추가 방법
여기서 실현된add방법은 간단한add(E)와add(int index, E) 두 가지 방법입니다.addAll()은 다른 집합을 LinkedList로 전환하는 방법으로 잠시 후에 실현합니다.
add 방법은 두 가지 재부팅 방법으로 각각 다른 추가 방식에 대응한다.먼저 add(E) 방법의 실현을 말해라.

 public boolean add(E element) {
 addAtLast(element);
 return true;
 }

요소를 추가할 위치를 지정하지 않으면 체인 테이블의 마지막에 기본적으로 추가됩니다.addAtLast의 핵심 코드는 다음과 같습니다.

 private void addAtLast(E element) {
 Node<E> l = last;
 Node<E> node = new Node<E>(element, null, l);
 last = node;
 if (l == null) {
 first = node;
 } else {
 l.next = node;
 }
 size++;
 }

먼저 마지막 노드 요소를 찾은 다음에 요소에 따라 새로운 노드 요소를 만듭니다. 그next는null,prev는마지막 노드 요소를 가리킵니다.Node 요소를 생성한 후에last는 먼저 생성된 Node 요소가 됩니다. 다음은 새로운 node 요소를 체인 테이블에 추가하면 됩니다.즉 l 대상(원래 마지막 위치, 현재 꼴찌 두 번째 요소의next 바늘, 새로운 node 요소를 가리키는 것)을 가리킨다.이로써 새 node 원소의next는null,prev는 꼴찌 두 번째 원소,꼴찌 두 번째 원소의next는 새 node를 가리키며node를 체인 테이블에 성공적으로 추가합니다.
상술한 조작을 통해 알 수 있듯이 삽입된 조작은 시간을 매우 절약하고 Array List보다 용량을 확대하고 원소를 이동하는 것이 매우 빠르다.
add의 두 번째 재부팅 방법add(int index, E e), 코드 구현을 먼저 보십시오.

 public void add(int index, E element) {
 checkRangeForAdd(index);
 if (index == size) {
 addAtLast(element);
 } else {
 Node<E> l = node(index);
 addBeforeNode(element, l);
 }
 }

우선 삽입할 index가 범위 내에 있는지 판단하고 있으면 후속add 작업을 수행합니다.삽입할 index가 마침 마지막 자리라면, 위에서 말한 addAtLast를 실행하고, 그렇지 않으면 index에 대응하는 Node 요소를 받아서addBeforeNode를 실행합니다.
index에 대응하는 Node 요소를 가져오는 방법은 다음과 같습니다.

 private Node<E> node(int index) {
 if (index < (size << 1)) {
 Node<E> cursor = first;
 for (int i = 0; i < index; i++) {
 cursor = cursor.next;
 }
 return cursor;
 } else {
 Node<E> cursor = last;
 for (int i = size - 1; i > index; i--) {
 cursor = cursor.prev;
 }
 return cursor;
 }
 }

이곳의 검색은 2분 검색을 채택하여 검색 시간을 절약할 뿐만 아니라 쌍방향 체인표의 특징에도 응용되었다.우선 인덱스가 앞부분의 범위에 있는지 뒤부분의 범위에 있는지 판단한다.만약에 앞쪽이라면 커서 Node는 처음에first이고 커서 Node 원소의next로 index가 있는 원소를 계속 가리킨다.만약 뒷반이라면 커서 Node는 처음에last이고 커서 Node 원소의prev로 index가 있는 원소를 계속 가리킨다.
지정된 요소 앞에 새 노드의 addBeforeNode를 삽입하는 방법은 다음과 같습니다.

 private void addBeforeNode(E element, Node<E> specifiedNode) {
 Node<E> preNode = specifiedNode.prev;
 Node<E> newNode = new Node<>(element, specifiedNode, preNode);
 if (preNode == null) {
 first = newNode;
 } else {
 preNode.next = newNode;
 }
 specifiedNode.prev = newNode;
 size++;
 }

삽입 방식은 매우 간단합니다. 새 노드의prev는 원 index 요소의prev이고, 새 노드의next는 원 index 요소입니다.나머지 작업은 이 node를 체인 테이블에 넣고 원래 index 요소인prev의next를 새 노드로 만들지만 preNode가 비어 있는지 판단하려면 newNode를 첫 번째 요소인first를 표시합니다.
이로써add방법 하나로 완성되었습니다.
get 방법
get 방법은 상술한 node 방법이 생긴 후에 매우 간단하다.코드는 다음과 같습니다.

 public E get(int index) {
 checkRange(index);
 return node(index).item;
 }

checkRange는 index가 범위에 없는지 확인합니다.

 private void checkRange(int index) {
 if (index >= size || index < 0) {
 throw new IndexOutOfBoundsException(" index ");
 }
 }

indexOf 방법
indexOf(Object o)는 지정된 요소의 아래 첨자를 가져오는 데 사용됩니다.

 public int indexOf(Object element) {
 Node<E> cursor = first;
 int count = 0;
 while (cursor != null) {
 if (element != null) {
 if (element.equals(cursor.item)) {
  return count;
 }
 }else{
 if (cursor.item == null) {
  return count;
 }
 }
 count ++;
 cursor = cursor.next;
 }
 return -1;
 }

Array List와 마찬가지로 첫 번째 위치부터 찾으려면 먼저 요소가null인지 아닌지를 판단하고 두 가지 상황으로 나눈다.
제거 방법
remove 방법은add 방법과 마찬가지로 두 가지 재부팅 방법이 있습니다. remove(Objecto)와remove(int index)
간단한 remove(int index) 방법을 먼저 보십시오. 코드는 다음과 같습니다.

 public E remove(int index) {
 checkRange(index);
 return deleteLink(index);
 }

deleteLink는 이 index에 대응하는 노드의 링크를 삭제하는 방법입니다. 코드는 다음과 같습니다.

 private E deleteLink(int index) {
 Node<E> l = node(index);
 E item = l.item;
 Node<E> prevNode = l.prev;
 Node<E> nextNode = l.next;
 if (prevNode == null) {
 first = nextNode;
 }else{
 prevNode.next = nextNode;
 l.next = null;
 }
 if (nextNode == null) {
 last = prevNode;
 }else{
 nextNode.prev = prevNode;
 l.prev = null;
 }
 size--;
 l.item = null;
 return item;
 }

먼저 이 index에 대응하는 Node 원소를 얻고 이 Node 원소의 이전 원소와 다음 원소를 얻습니다.다음은 앞의 원소와 뒤의 원소를 직접 연결하기만 하면 되고, 다른 것은 앞의 원소와 뒤의 원소가null인지 아닌지를 추가로 판단하면 된다.이전 원소가null인지 아닌지를 판단할 때 이전 원소만 조작하고, 다음 원소가null인지 아닌지를 판단할 때도 다음 원소만 조작하면 된다.마지막으로, 삭제할 요소의 각각은null로 인용됩니다.
remove의 또 다른 재부팅 방법인 remove(Object o)는 index Of와 delete Link 방법을 실현한 후에 매우 간단하다.

 public boolean remove(Object o) {
 int index = indexOf(o);
 if (index < 0){
 return false;
 }
 deleteLink(index);
 return true;
 }

이 요소에 대응하는 아래 표를 가져오고 deleteLink 방법을 실행하여remove 작업을 완성합니다.
총결산
이로써 하나의 기능이 간단한 LinkedList가 완성되었고 모든 코드는 볼 수 있다소스 주소.
이상은 본문의 전체 내용입니다. 본고의 내용이 여러분의 학습이나 업무에 일정한 도움을 줄 수 있는 동시에 저희를 많이 지지해 주시기 바랍니다!