썸넬 img ref :
https://blog.masaischool.com/linked-list/
🌱 List
중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용됩니다. List 인터페이스를 구현한 클래스로 대표적으로 ArrayList와 LinkedList가 있습니다. 이 외에 Vector가 있고 Vector를 구현한 Stack까지 상속 계층도에 있습니다.
🌿 List 메서드
(추가) void clear() : 모든 요소 삭제
🌿 ArrayList vs Vector
Vector 클래스는 자바 컬렉션 프레임워크가 나오기 전부터 있었던 클래스이고, ArrayList 클래스는 Vector 클래스의 단점을 보완하기 위해 나온 클래스입니다.
▶ 공통점
- 순서를 유지하고, 중복을 허용
- Iterator 를 사용할 수 있음
- 초기 용량 10
▶ 차이점
| Vector | ArrayList |
|---|---|
| Thread-safe | Thread-unsafe |
| 용량 초과 시 2배 늘림 | 용량 초과 시 1.5배 늘림 |
| Enumeration O | Enumeration X |
(Enumeration : Iterator의 구버전)
🔎 Thread-safe
멀티쓰레드 프로그래밍에서 여러 쓰레드가 공유 자원을 사용할 때, 작업 후 원하는 결과가 나오도록 하는 것을 보장하는 성질입니다. 이를 위해 '임계 영역', '락(Lock)' 등을 사용하여 한 작업의 결과가 일관성있게 반영되도록 합니다. 하지만 Thread-unsafe 보다 속도가 느리기 때문에 멀티쓰레드 환경이 아니라면 굳이 사용할 필요가 없습니다.
Vector 클래스는 컬렉션 프레임워크 이전에 나온 클래스이고, 현재 소스 코드 호환 때문에 남아 있는 클래스이기 때문에 ArrayList를 사용하자
🌿 ArrayList vs LinkedList
[공통점]
1. 동일한 특성의 데이터들을 묶는다.
2. 반복문 내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다.
[차이점 - 배열]
1. 처음 선언한 배열의 크기를 변경할 수 없다. (정적 할당)
2. 메모리에 연속적으로 나열되어 할당됨
3. 삭제 후 index가 연속적으로 정렬되지 않는다.
[차이점 - 리스트]
1. 리스트의 길이가 가변적 (동적 할당)
2. 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지 않고 각 데이터들은 주소로 연결되어 있다.)
3. 데이터 사이에 빈 공간이 허용되지 않는다.
[배열의 장단점]
<장점>
1. 데이터 크기가 정해져 있을 경우 메모리 관리가 편리
2. 메모리에 연속적으로 나열되어 할당하기 때문에 index를 통한 색인(접근)속도가 빠름
3. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠름
<단점>
1. 정적 할당, 데이터 양에 따라 유연하게 대처할 수 없음
2. 삽입 또는 삭제 후 데이터 재정렬 작업이 필요함(안 그러면 빈 공간 발생)
[리스트의 장단점]
<장점>
1. 동적 할당, 메모리 관리가 편리함
2. 빈 공간을 허용하지 않기 때문에 데이터 관리에도 편리
3. 각 데이터가 연결되어 있으므로 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에 삽입, 삭제가 용이함 (ArrayList는 예외)
4. 중간 데이터의 추가/삭제는 ArrayList보다 빠름
<단점>
1. 객체로 데이터를 다루기 때문에 적은 양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 커진다.
(JVM에선 객체의 헤더(8Byte), 원시 필드(4Byte), 패딩(4Byte)으로 최소 16Byte를 차지한다. 거기에다가 객체 데이터들을 다시 주소로 연결하기 때문에 16 + a가 된다.)
2. 기본적으로 주소를 기반으로 구성되어 있고, 메모리에 순차적으로 할당하는 것이 아니므로 색인(검색) 능력은 떨어진다.
ref :
https://st-lab.tistory.com/146
https://st-lab.tistory.com/161
🌿 ArrayList 메소드
📌 nCopies()
nCopies(Capacity, InitialValue)
ArrayList<Integer> check = new ArrayList<>(Collections.nCopies(10, 0));🌿 ArrayList 구현
📌 List Interface
코드package interface_form;
public interface ListInterface<E> {
/**
* 리스트에 요소를 추가
*
* @param value 리스트에 추가할 요소
* @return 리스트에서 중복을 허용하지 않을 경우
* 리스트에 이미 중복되는 요소가 있을 경우 {@code false} 반환
* 중복되는 원소가 없을 경우 {@code true} 반환
*/
boolean add(E value);
/**
* 리스트에 요소를 특정 위치에 추가
* 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀림
*
* @param index 리스트에 요소를 추가할 특정 위치 변수
* @param value 리스트에 추가할 요소
*/
void add(int index, E value);
/**
* 리스트에서 특정 요소를 삭제
* 동일한 요소가 여러 개일 경우, 가장 처음 발견한 요소만 삭제
*
* @param value 리스트에서 삭제할 요소
* @return 리스트에서 삭제할 요소가 없거나 삭제에 실패할 경우 {@code false}
* 삭제에 성공할 경우 {@code true}
* */
boolean remove(Object value);
/**
* 리스트에서 특정 위치에 있는 요소를 새 요소로 대체
*
* @param index 리스트에 접근할 위치 변수
* @param value 새로 대체할 요소 변수
* */
void set(int index, E value);
/**
* 리스트에서 특정 요소가 존재하는지 여부를 확인
*
* @param value 리스트에서 찾을 특정 요소 변수
* @return 리스트에 특정 요소가 존재할 경우 {@code true}
* 존재하지 않을 경우 {@code false}
*/
boolean contains(Object value);
/**
* 리스트에 특정 요소가 몇 번째 위치에 있는지를 반환
*
* @param value 리스트에서 위치를 찾을 요소 변수
* @return 리스트에서 처음으로 요소와 일치하는 위치를 반환
* 만약 일치하는 요소가 없을 경우 -1 반환
* */
int indexOf(Object value);
/**
* 리스트에 있는 요소의 개수를 반환
*
* @return 리스트에 있는 요소 개수를 반환
* */
int size();
/**
* 리스트에 요소가 비어있는지를 반환
*
* @return 리스트에 요소가 없을 경우 {@code true}, 있을 경우 {@code false}
*/
boolean isEmpty();
/**
* 리스트에 있는 요소를 모두 삭제
* */
void clear();
}
📌 ArrayList
코드package list.arrayList;
import interface_form.ListInterface;
import java.util.Arrays;
public class ArrayList<E> implements ListInterface<E>, Cloneable {
private static final int DEFAULT_CAPACITY = 10; //최소(기본) 용적 크기
private static final Object[] EMPTY_ARRAY = {}; //빈 배열
private int size; //요소 개수
Object[] array; //요소를 담을 배열
//생성자1 (초기 공간 할당x)
public ArrayList() {
this.array = EMPTY_ARRAY;
this.size = 0;
}
//생성자2 (초기 공간 할당o)
public ArrayList(int capacity) {
this.array = new Object[capacity];
this.size = 0;
}
private void resize() {
int array_capacity = array.length;
//if array's capacity is 0
if (Arrays.equals(array, EMPTY_ARRAY)) {
array = new Object[DEFAULT_CAPACITY];
return;
}
//용량 Fulled
if (size == array_capacity) {
int new_capacity = array_capacity * 2; //doubling
//copy
array = Arrays.copyOf(array, new_capacity);
return;
}
//용적의 절반 미만으로 요소가 차지하고 있을 경우
if (size < (array_capacity / 2)) {
int new_capacity = array_capacity / 2;
//copy
array = Arrays.copyOf(array, Math.max(new_capacity, DEFAULT_CAPACITY));
return;
}
}
@Override
public boolean add(E value) {
addLast(value);
return true;
}
public void addLast(E value) {
//꽉차있는 상태라면 용적 재할당
if (size == array.length) {
resize();
}
array[size] = value; //마지막 위치에 요소 추가
size++;
}
@Override
public void add(int index, E value) {
//size보다 크면 빈 공간이 생김
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == size) { //마지막 위치에 삽입
addLast(value);
} else { //중간 삽입
if (size == array.length) { //Fulled
resize();
}
//index 기준 뒤에 있는 요소들 1칸 back
for (int i = size; i > index; i--) {
array[i] = array[i - 1];
}
array[index] = value; //index 위치에 요소 삽입
size++;
}
}
public void addFirst(E value) {
add(0, value);
}
@SuppressWarnings("unchecked")
@Override
public E remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
E elem = (E) array[index];
array[index] = null; //삭제
//빈 공간 메꾸기
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
array[i + 1] = null;
}
size--;
resize();
return elem;
}
@Override
public boolean remove(Object value) {
int index = indexOf(value);
if (index == -1) {
return false;
}
remove(index);
return true;
}
@SuppressWarnings("unchecked")
@Override
public E get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
return (E) array[index];
}
@Override
public void set(int index, E value) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
} else {
//해당 위치의 요소를 교체
array[index] = value;
}
}
@Override
public boolean contains(Object value) {
return indexOf(value) > -1;
}
//front -> back 탐색
@Override
public int indexOf(Object value) {
for (int i = 0; i < size; i++) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
//back -> front 탐색
public int lastIndexOf(Object value) {
for (int i = size - 1; i >= 0; i--) {
if (array[i].equals(value)) {
return i;
}
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (int i = 0; i < size; i++) {
array[i] = null;
}
size = 0;
resize();
}
@Override
public Object clone() throws CloneNotSupportedException {
//새로운 객체 생성
ArrayList<?> cloneList = (ArrayList<?>)super.clone();
//새로운 객체의 배열도 생성해주어야 함 (객체는 얕은 복사가 되기 때문)
cloneList.array = new Object[size];
//배열의 값을 복사(Deep cloning)
System.arraycopy(array, 0, cloneList.array, 0, size);
return cloneList;
}
public Object[] toArray() {
return Arrays.copyOf(array, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
return (T[]) Arrays.copyOf(array, size, a.getClass());
}
System.arraycopy(array, 0, a, 0, size);
return a;
}
}
📌 ArrayList - 테스트 및 설명
코드package list.arrayList;
import java.util.Arrays;
public class ArrayListApplication {
@SuppressWarnings("unchecked")
public static void main(String[] args) throws CloneNotSupportedException {
ArrayList<Integer> original = new ArrayList<>();
original.add(10);
ArrayList<Integer> copy = original;
ArrayList<Integer> clone = (ArrayList<Integer>) original.clone();
copy.add(20);
clone.add(30);
System.out.println("original list");
for (int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + original.get(i));
}
System.out.println("\ncopy list");
for (int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + copy.get(i));
}
System.out.println("\nclone list");
for (int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + clone.get(i));
}
System.out.println("\noriginal list reference : " + original);
System.out.println("copy list reference : " + copy);
System.out.println("clone list reference : " + clone);
ArrayList<String> bucket = new ArrayList<>();
bucket.add("apple");
bucket.add("banana");
bucket.add("orange");
bucket.add(1, "strawberry");
System.out.println("\nArray : " + Arrays.toString(bucket.toArray()));
System.out.println("\nstrawberry 인덱스 = " + bucket.indexOf("strawberry"));
System.out.println("bucket.get(2) = " + bucket.get(2));
System.out.println("bucket.size() = " + bucket.size());
System.out.println("---remove index 1---");
System.out.println("removed value : " + bucket.remove(1));
System.out.println("\nArray : " + Arrays.toString(bucket.toArray()));
bucket.set(1, "grape");
System.out.println("\nArray : " + Arrays.toString(bucket.toArray()));
System.out.println("banana is existing? " + bucket.contains("banana"));
bucket.remove("apple");
System.out.println("\nArray : " + Arrays.toString(bucket.toArray()));
bucket.clear();
System.out.println("\nArray : " + Arrays.toString(bucket.toArray()));
}
}
🔎 Object.clone
Object 클래스에서 객체의 클로닝을 위해 제공하는 메소드입니다. 객체 생성을 위해 객체의 생성자 메소드를 실행하지 않으며, 객체가 유지하고 있는 상태값들을 그대로 복사하게 됩니다. 이때 복사되는 원래 객체에는 아무런 변화를 주지 않습니다. 또한, 원본의 필드와 완전히 같은 값으로 초기화합니다.
그러나 이 메소드는 객체 구조는 복사하지만 객체 레퍼런스의 경우 레퍼런스만 복사합니다. 즉, 객체 레퍼런스가 가리키고 있는 실제 객체는 복사하지 않습니다. 이것을 shallow cloning(얕은 복제)라고 하며, 레퍼런스로 가리키는 객체까지 모두 복사하는 deep cloning(깊은 복제)과 구별됩니다.
▶ Shallow cloning
필드 멤버가 모두 primitive type인 경우에 유용
(primitive type은 객체의 레퍼런스를 저장하지 않음)
shallow cloning 은 원본에서 새로운 배열을 생성하지 않고 원본에서 생성된 배열을 공유하기 때문에 원본이나 클론에 값이 추가되거나 삭제되면 서로 영향을 줍니다.
public class MyNumbers implements Cloneable {
private int[] numbers = null;
public MyNumbers() {
numbers = new int[10];
}
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
}▶ Deep cloning
super.clone() 으로 Object.clone() 메소드를 호출하여 완전한 객체 구조를 복사
super.clone() 으로 완전한 복제가 된 클로닝 객체와 그 객체의 배열을 생성한 후 원본 배열을 클로닝의 배열로 복사하면 됩니다.
public Object clone() throws CloneNotSupportedException {
MyNumber myObj = super.clone();
myObj.numbers = (int[]) numbers.clone();
return myObj;
}▶ CloneNotSupportedException
clone() 메소드에서 발생할 수 있는 예외로 Cloneable 인터페이스를 구현하지 않았거나, 상속된 클래스가 클로닝될 수 없음을 나타내기 위하여 일부러 발생시키는 경우입니다.
Object.clone() 메소드는 Object 클래스에서 구현되어 있으므로 Cloneable 인터페이스를 구현함으로써 clone() 메소드를 호출할 수 있게 되며, 대부분의 경우 clone() 메소드를 오버라이딩하여 사용하게 됩니다. 또한, 배열은 기본적으로 Cloneable 인터페이스를 구현했으므로 클로닝이 가능합니다. 따라서, 해당 예외가 발생할 원인이 없습니다.
🌿 Singly LinkedList
📌 Node 구현
package list.linkedList;
public class Node<E> {
E data;
Node<E> next;
public Node(E data) {
this.data = data;
this.next = null;
}
}
📌 Singly LinkedList 구현
코드package list.linkedList;
import interface_form.ListInterface;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class SinglyLinkedList<E> implements ListInterface<E>, Cloneable {
private Node<E> head; //노드의 첫 부분
private Node<E> tail; //노드의 끝 부분
private int size; //요소 개수
public SinglyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
//특정 위치의 노드를 반환
private Node<E> search(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> x = head; //head부터 시작
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
@Override
public boolean add(E value) {
addLast(value);
return true;
}
public void addLast(E value) {
Node<E> newNode = new Node<>(value);
if (size == 0) { //첫 노드일 경우
addFirst(value);
return;
}
//Connection 작업
tail.next = newNode;
tail = newNode;
size++;
}
@Override
public void add(int index, E value) {
//tail 뒤에 추가하는 경우도 있으므로, size index 까지 허용
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == 0) { //첫 노드일 경우
addFirst(value);
return;
}
if (index == size) { //마지막 위치에 추가
addLast(value);
return;
}
//Connection 작업
Node<E> prev_node = search(index - 1);
Node<E> next_node = prev_node.next;
Node<E> newNode = new Node<>(value);
prev_node.next = null; //이전 노드의 링크 제거
prev_node.next = newNode; //이전 노드의 링크 수정
newNode.next = next_node; //삽입 위치 노드의 링크 수정
size++;
}
public void addFirst(E value) {
Node<E> newNode = new Node<>(value);
newNode.next = head;
head = newNode;
size++;
//추가하는 노드가 첫 노드일 경우
if (head.next == null) {
tail = head;
}
}
//가장 앞에 있는 노드 제거
public E remove() {
Node<E> headNode = head;
if (headNode == null) {
throw new NoSuchElementException();
}
E elem = headNode.data; //삭제될 노드
Node<E> nextNode = head.next;
//head 삭제
head.data = null;
head.next = null;
//리스트 갱신
head = nextNode;
size--;
if (size == 0) { //삭제함으로써 빈 리스트가 된 경우
tail = null;
}
return elem;
}
@Override
public E remove(int index) {
//삭제하려는 원소가 첫 번째 원소일 경우
if (index == 0) {
return remove();
}
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> prev_node = search(index - 1);
Node<E> removedNode = prev_node.next; //삭제할 노드
Node<E> next_node = removedNode.next;
E elem = removedNode.data;
prev_node.next = next_node; //링크 갱신
if (prev_node.next == null) { //삭제할 노드가 last index's 노드라면
tail = prev_node;
}
//노드 삭제
removedNode.next = null;
removedNode.data = null;
size--;
return elem;
}
@Override
public boolean remove(Object value) {
Node<E> prev_node = head;
Node<E> x = head;
for (; x != null; x = x.next) {
if (value.equals(x.data)) {
break;
}
prev_node = x; //prev_node를 1칸씩 당기기 위함
}
//일치하는 요소가 없을 경우
if (x == null) {
return false;
}
if (x.equals(head)) {
remove();
return true;
} else {
prev_node.next = x.next; //링크 수정
if (prev_node.next == null) { //삭제할 노드가 last index's 노드라면
tail = prev_node;
}
//노드 삭제
x.data = null;
x.next = null;
size--;
return true;
}
}
@Override
public E get(int index) {
return search(index).data;
}
@Override
public void set(int index, E value) {
Node<E> replaceNode = search(index);
replaceNode.data = null;
replaceNode.data = value;
}
@Override
public boolean contains(Object value) {
return indexOf(value) >= 0;
}
@Override
public int indexOf(Object value) {
int index = 0;
for (Node<E> x = head; x != null; x = x.next) {
if (value.equals(x.data)) {
return index;
}
index++;
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (Node<E> x = head; x != null; x = x.next) {
Node<E> nextNode = x.next;
x.data = null;
x.next = null;
x = nextNode;
}
head = tail = null;
size = 0;
}
@Override
protected Object clone() throws CloneNotSupportedException {
@SuppressWarnings("unchecked")
SinglyLinkedList<? super E> clone = (SinglyLinkedList<? super E>) super.clone();
clone.head = null;
clone.tail = null;
clone.size = 0;
for (Node<E> x = head; x != null; x = x.next) {
clone.addLast(x.data);
}
return clone;
}
public Object[] toArray() {
Object[] array = new Object[size];
int idx = 0;
for (Node<E> x = head; x != null; x = x.next) {
array[idx++] = (E) x.data;
}
return array;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
Object[] result = a;
for (Node<E> x = head; x != null; x = x.next) {
result[i++] = x.data;
}
return a;
}
public void sort() {
sort(null);
}
@SuppressWarnings({"unchecked", "rawtypes"})
public void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
int i = 0;
for (Node<E> x = head; x != null; x = x.next, i++) {
x.data = (E) a[i];
}
}
}
📌 Singly LinkedList - 테스트 및 설명
코드package list.linkedList;
import list.arrayList.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class SinglyLinkedListApplication {
@SuppressWarnings("unchecked")
public static void main(String[] args) throws CloneNotSupportedException {
SinglyLinkedList<Integer> original = new SinglyLinkedList<>();
original.add(10);
SinglyLinkedList<Integer> copy = original;
SinglyLinkedList<Integer> clone = (SinglyLinkedList<Integer>) original.clone();
copy.add(20);
clone.add(30);
System.out.println("original list");
for (int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + original.get(i));
}
System.out.println("\ncopy list");
for (int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + copy.get(i));
}
System.out.println("\nclone list");
for (int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + clone.get(i));
}
System.out.println("\noriginal list reference : " + original);
System.out.println("copy list reference : " + copy);
System.out.println("clone list reference : " + clone);
System.out.println();
SinglyLinkedList<Student> list = new SinglyLinkedList<>();
list.add(new Student("김자바", 92));
list.add(new Student("이시플", 72));
list.add(new Student("조시샵", 98));
list.add(new Student("파이손", 51));
list.sort(comp);
printList(list);
System.out.println("\nlist.size() = " + list.size());
System.out.println("list.get(1) = " + list.get(1));
System.out.println("\n***index 2 데이터 변경***");
list.set(2, new Student("이플플", 75));
printList(list);
list.clear();
System.out.println("\nafter clear() = " + Arrays.toString(list.toArray()));
System.out.println("list.isEmpty() = " + list.isEmpty());
System.out.println("\n***Masking***");
list.add(new Student("김OO", 92));
list.add(new Student("이OO", 72));
list.add(new Student("조OO", 98));
list.add(new Student("파OO", 51));
list.sort();
printList(list);
System.out.println("\n***remove()***");
list.remove();
printList(list);
}
private static void printList(SinglyLinkedList<Student> list) {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
//sort 방법 1
static Comparator<Student> comp = (o1, o2) -> o2.score - o1.score;
static class Student implements Comparable<Student> {
String name;
int score;
Student(String name, int score) {
this.name = name;
this.score = score;
}
public String toString() {
return "이름 : " + name + "\t성적 : " + score;
}
@Override
public int compareTo(Student o) {
return o.score - this.score;
}
}
}
🌿 Doubly LinkedList
양방향으로 연결되어 Singly LinkedList에 비해 검색(색인)능력이 좋아집니다.
📌 Node 구현
package list.linkedList.doubly;
public class Node<E> {
E data;
Node<E> next;
Node<E> prev;
public Node(E data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
📌 Doubly LinkedList 구현
코드package list.linkedList.doubly;
import interface_form.ListInterface;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class DoublyLinkedList<E> implements ListInterface<E>, Cloneable {
private Node<E> head;
private Node<E> tail;
private int size;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
private Node<E> search(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
//reverse tracking
if (index > size / 2) {
Node<E> x = tail;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
//in order tracking
else {
Node<E> x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
}
public void addFirst(E value) {
Node<E> newNode = new Node<>(value);
newNode.next = head;
if (head != null) {
head.prev = newNode;
}
head = newNode;
size++;
//newNode 가 첫 노드
if (head.next == null) {
tail = head;
}
}
@Override
public boolean add(E value) {
addLast(value);
return true;
}
public void addLast(E value) {
Node<E> newNode = new Node<>(value);
if (size == 0) {
addFirst(value);
return;
}
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
size++;
}
@Override
public void add(int index, E value) {
//addLast case 를 고려하여 size index 허용
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(value);
return;
}
if (index == size) {
addLast(value);
return;
}
Node<E> prev_node = search(index - 1); //추가하려는 위치의 이전 노드
Node<E> next_node = prev_node.next; //추가하려는 위치의 노드
Node<E> newNode = new Node<>(value);
//링크 제거
prev_node.next = null;
next_node.prev = null;
//링크 수정
prev_node.next = newNode;
newNode.prev = prev_node;
newNode.next = next_node;
next_node.prev = newNode;
size++;
}
public E remove() {
Node<E> headNode = head;
if (headNode == null) {
throw new NoSuchElementException();
}
E elem = headNode.data; //반환용 데이터
Node<E> nextNode = head.next;
//head 삭제
head.data = null;
head.next = null;
if (nextNode != null) { //NPE 방지
nextNode.prev = null;
}
head = nextNode;
size--;
//삭제 후 빈 리스트가 된 경우
if (size == 0) {
tail = null;
}
return elem;
}
@Override
public E remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
E elem = head.data;
remove();
return elem;
}
Node<E> prevNode = search(index - 1); //삭제할 노드의 이전 노드
Node<E> removedNode = prevNode.next; //삭제할 노드
Node<E> nextNode = removedNode.next; //삭제할 노드의 다음 노드
E elem = removedNode.data; //반환용 데이터
/*
* index = 0 과 index < 0 인 경우는 이미 필터링됨
* 즉, 분기 이후 prevNode 는 항상 존재함
*
* 링크 제거 및 삭제
* */
prevNode.next = null;
removedNode.next = null;
removedNode.prev = null;
removedNode.data = null;
//링크 삭제 + 수정
if (nextNode != null) {
nextNode.prev = null;
nextNode.prev = prevNode;
prevNode.next = nextNode;
}
//마지막 위치의 노드를 삭제한 경우
else {
tail = prevNode;
}
size--;
return elem;
}
@Override
public boolean remove(Object value) {
Node<E> prevNode = head;
Node<E> x = head;
for (; x != null; x = x.next) {
if (value.equals(x.data)) {
break;
}
prevNode = x;
}
//일치하는 요소가 없을 경우
if (x == null) {
return false;
}
if (x.equals(head)) {
remove();
return true;
} else { //remove(int index)
Node<E> nextNode = x.next;
//링크 및 데이터 제거
prevNode.next = null;
x.data = null;
x.next = null;
x.prev = null;
if (nextNode != null) {
nextNode.prev = null;
nextNode.prev = prevNode;
prevNode.next = nextNode;
}
//마지막 위치의 노드를 삭제한 경우
else {
tail = prevNode;
}
size--;
return true;
}
}
@Override
public E get(int index) {
return search(index).data;
}
@Override
public void set(int index, E value) {
Node<E> replaceNode = search(index);
replaceNode.data = null;
replaceNode.data = value;
}
@Override
public boolean contains(Object value) {
return indexOf(value) >= 0;
}
@Override
public int indexOf(Object value) {
int index = 0;
for (Node<E> x = head; x != null; x = x.next) {
if (value.equals(x.data)) {
return index;
}
index++;
}
return -1;
}
public int lastIndexOf(Object value) {
int index = size;
for (Node<E> x = tail; x != null; x = x.prev) {
index--;
if (value.equals(x.data)) {
return index;
}
}
return -1;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (Node<E> x = head; x != null;) {
Node<E> nextNode = x.next;
x.data = null;
x.next = null;
x.prev = null;
x = nextNode;
}
head = tail = null;
size = 0;
}
@Override
protected Object clone() throws CloneNotSupportedException {
@SuppressWarnings("unchecked")
DoublyLinkedList<? super E> clone = (DoublyLinkedList<? super E>) super.clone();
clone.head = null;
clone.tail = null;
clone.size = 0;
for (Node<E> x = head; x != null; x = x.next) {
clone.addLast(x.data);
}
return clone;
}
public Object[] toArray() {
Object[] array = new Object[size];
int idx = 0;
for (Node<E> x = head; x != null; x = x.next) {
array[idx++] = (E) x.data;
}
return array;
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
}
int i = 0;
Object[] result = a;
for (Node<E> x = head; x != null; x = x.next) {
result[i++] = x.data;
}
return a;
}
public void sort() {
sort(null);
}
@SuppressWarnings({"unchecked", "rawtypes"})
public void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
int i = 0;
for (Node<E> x = head; x != null; x = x.next) {
x.data = (E) a[i];
}
}
}
📌 Doubly LinkedList - 테스트 및 설명
코드package list.linkedList.doubly;
import java.util.Arrays;
import java.util.Comparator;
public class DoublyLinkedListApplication {
@SuppressWarnings("unchecked")
public static void main(String[] args) throws CloneNotSupportedException {
DoublyLinkedList<Integer> original = new DoublyLinkedList<>();
original.add(10);
DoublyLinkedList<Integer> copy = original;
DoublyLinkedList<Integer> clone = (DoublyLinkedList<Integer>) original.clone();
copy.add(20);
clone.add(30);
System.out.println("original list");
for(int i = 0; i < original.size(); i++) {
System.out.println("index " + i + " data = " + original.get(i));
}
System.out.println("\ncopy list");
for(int i = 0; i < copy.size(); i++) {
System.out.println("index " + i + " data = " + copy.get(i));
}
System.out.println("\nclone list");
for(int i = 0; i < clone.size(); i++) {
System.out.println("index " + i + " data = " + clone.get(i));
}
System.out.println("\noriginal list reference : " + original);
System.out.println("copy list reference : " + copy);
System.out.println("clone list reference : " + clone);
DoublyLinkedList<Student> list = new DoublyLinkedList<>();
list.add(new Student("김자바", 92));
list.add(new Student("이시플", 72));
list.add(new Student("조시샵", 98));
list.add(new Student("파이손", 51));
list.sort(comp);
System.out.println();
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
System.out.println("\nlist.size() = " + list.size());
System.out.println("list.get(2) = " + list.get(2));
list.clear();
System.out.println("after clear() = " + list.isEmpty());
System.out.println("\n***Masking***");
list.add(new Student("김OO", 92));
list.add(new Student("이OO", 72));
list.add(1, new Student("조OO", 98));
list.add(2, new Student("파OO", 51));
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
list.remove();
System.out.println("\n***remove()***");
System.out.println("list.toArray() = " + Arrays.toString(list.toArray()));
Object[] a = new Object[10];
System.out.println("New Array = " + Arrays.toString(list.toArray(a)));
list.remove(1);
System.out.println("\n***remove(1)***");
System.out.println("list.toArray() = " + Arrays.toString(list.toArray()));
}
static Comparator<Student> comp = (o1, o2) -> o2.score - o1.score;
static class Student implements Comparable<Student> {
String name;
int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public String toString() {
return "이름 : " + name + "\t성적 : " + score;
}
@Override
public int compareTo(Student o) {
return o.score - this.score;
}
}
}
@SuppressWarnings("rawtypes")
제네릭을 사용하는 클래스 매개 변수가 불특정일 때의 경고 억제
ref : https://crosstheline.tistory.com/89
