Doubly LinkedList
단일 연결리스트와 달리 '이전 노드'를 가리키는 변수가 추가된 양방향 리스트
- 단일 연결리스트에 비해 검색(색인) 능력이 좋아진다.
- 이전 노드를 가리키는 변수를 갖고 있기 때문에 tail부터 탐색할 수 있다. (좀 더 효율적)
package Interface_form;
/**
*
* 자바 List Interface입니다. <br>
* List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다.
*
* @author st_lab
* @param <E> the type of elements in this list
*
* @version 1.0
*
*/
public interface List<E> {
/**
* 리스트에 요소를 추가합니다.
*
* @param value 리스트에 추가할 요소
* @return 리스트에서 중복을 허용하지 않을 경우에 리스트에 이미 중복되는
* 요소가 있을 경우 {@code false}를 반환하고, 중복되는 원소가
* 없을경우 {@code true}를 반환
*/
boolean add(E value);
/**
* 리스트에 요소를 특정 위치에 추가합니다.
* 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀립니다.
*
* @param index 리스트에 요소를 추가할 특정 위치 변수
* @param value 리스트에 추가할 요소
*/
void add(int index, E value);
/**
* 리스트의 index 위치에 있는 요소를 삭제합니다.
*
* @param index 리스트에서 삭제 할 위치 변수
* @return 삭제된 요소를 반환
*/
E remove(int index);
/**
* 리스트에서 특정 요소를 삭제합니다. 동일한 요소가
* 여러 개일 경우 가장 처음 발견한 요소만 삭제됩니다.
*
* @param value 리스트에서 삭제할 요소
* @return 리스트에 삭제할 요소가 없거나 삭제에 실패할
* 경우 {@code false}를 반환하고 삭제에 성공할 경우 {@code true}를 반환
*/
boolean remove(Object value);
/**
* 리스트에 있는 특정 위치의 요소를 반환합니다.
*
* @param index 리스트에 접근할 위치 변수
* @return 리스트의 index 위치에 있는 요소 반환
*/
E get(int index);
/**
* 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
*
* @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();
/**
* 리스트에 있는 요소를 모두 삭제합니다.
*/
public void clear();
}
0. Node 구현 (Node.java)
class Node<E> {
E data;
Node<E> next; // 다음 노드객체를 가리키는 래퍼런스 변수
Node<E> prev; // 이전 노드객체를 가리키는 래퍼런스 변수
Node(E data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
1. 클래스 및 생성자 구성
import Interface_form.List;
public class DLinkedList<E> implements List<E> {
private Node<E> head; // 노드의 첫 부분
private Node<E> tail; // 노드의 마지막 부분
private int size; // 요소 개수
public DLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
1) Node<E> head : 리스트의 가장 첫 노드를 가리키는 변수
2) Node<E> tail : 리스트의 가장 마지막 노드를 가리키는 변수
3) sizd : 리스트에 연결된 노드의 개수
처음 연결리스트를 생성할 때에는 데이터가 없으므로 null, 0으로 초기화 진행
// 메인클래스에서 객체 생성 시
DLinkedList<Integer> list = new DLinkedList<>();
2. search
검색 과정에서 index값이 head에 가까운지 tail에 가까운지 구분하여 어디서 시작할지 정해서 탐색
// 특정 위치의 노드를 반환하는 메소드
private Node<E> search(int index) {
// 범위 밖(잘못된 위치)일 경우 예외 던지기
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 뒤에서부터 검색
if (index > size / 2) {
Node<E> x = tail;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
// 앞에서부터 검색
else {
Node<E> x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
}
3. add
public void addFirst(E value) {
Node<E> newNode = new Node<E>(value); // 새 노드 생성
newNode.next = head; // 새 노드의 다음 노드로 head 노드를 연결
/**
* head가 null이 아닐 경우에만 기존 head노드의 prev 변수가
* 새 노드를 가리키도록 한다.
* 이유는 기존 head노드가 없는 경우(null)는 데이터가
* 아무 것도 없던 상태였으므로 head.prev를 하면 잘못된 참조가 된다.
*/
if (head != null) {
head.prev = newNode;
}
head = newNode;
size++;
/**
* 다음에 가리킬 노드가 없는 경우(=데이터가 새 노드밖에 없는 경우)
* 데이터가 한 개(새 노드)밖에 없으므로 새 노드는 처음 시작노드이자
* 마지막 노드다. 즉 tail = head 다.
*/
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<E>(value); // 새 노드 생성
if (size == 0) { // 처음 넣는 노드일 경우 addFisrt로 추가
addFirst(value);
return;
}
/**
* 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 하고
* tail이 가리키는 노드를 새 노드로 바꿔준다.
*/
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
size++;
}
public void add(int index, E value) {
// 잘못된 인덱스를 참조할 경우 예외 발생
if (index > size || index < 0) {
throw new IndexOutOfBoundsException();
}
// 추가하려는 index가 가장 앞에 추가하려는 경우 addFirst 호출
if (index == 0) {
addFirst(value);
return;
}
// 추가하려는 index가 마지막 위치일 경우 addLast 호출
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<E>(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++;
}
1) 첫번째 위치 삽입 : addFirst(E value)
데이터를 이동시키는 것이 아닌 새로운 노드를 생성하고 새 노드의 레퍼런스 변수인 next가 head노드를 가리키도록 하고,
기존의 head노드의 prev는 head의 새노드를 가리키도록 업데이트한다.
2) 기본(마지막 위치) 삽입 : addLast(E value)
size=0일 경우(아무런 노드가 없는 경우)는 처음으로 데이터를 추가한다는 뜻이므로 addFirst()를 호출한다.
데이터를 이동시키는 것이 아닌 새로운 노드를 생성하고 이전 노드의 레퍼런스 변수가 새로운 노드를 가리키도록 한다.
3) 특정 위치에 추가 : add(int index, E value)
(넣으려는 위치의 앞 뒤로 링크를 새로 업데이트를 해주어야 하기 때문에 할 일이 가장 많다.)
- 넣으려는 위치의 이전 노드를 prev_Node라 하고, 넣으려는 위치의 기존 노드를 next_Node라고 칭한다.
- 이전 노드(prev_Node)의 next 변수는 새 노드(newNode)를 가리키도록 하고, 새 노드는 prev와 next를 앞 뒤 노드를 가리키도록 한 뒤 마지막으로 next_Node의 prev변수는 새 노드를 가리키도록 해야 한다.
- index변수가 잘못된 위치를 참조할 수 있기 때문에 IndexOutOfBoundException예외처리를 해준다.
4. remove
public E remove() {
Node<E> headNode = head;
if (headNode == null) {
throw new NoSuchElementException();
}
// 삭제된 노드를 반환하기 위한 임시 변수
E element = headNode.data;
// head의 다음 노드
Node<E> nextNode = head.next;
// head 노드의 데이터들을 모두 삭제
head.data = null;
head.next = null;
/**
* head의 다음노드(=nextNode)가 null이 아닐 경우에만
* prev 변수를 null로 업데이트 해주어야 한다.
* 이유는 nextNode가 없는 경우(null)는 데이터가
* 아무 것도 없던 상태였으므로 nextNode.prev를 하면 잘못된 참조가 된다.
*/
if(nextNode != null) {
nextNode.prev = null;
}
head = nextNode;
size--;
/**
* 삭제된 요소가 리스트의 유일한 요소였을 경우
* 그 요소는 head 이자 tail이었으므로
* 삭제되면서 tail도 가리킬 요소가 없기 때문에
* size가 0일경우 tail도 null로 변환
*/
if(size == 0) {
tail = null;
}
return element;
}
@Override
public E remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException();
}
// 삭제하려는 노드가 첫 번째 노드일 경우
if (index == 0) {
E element = head.data;
remove();
return element;
}
Node<E> prevNode = search(index - 1); // 삭제할 노드의 이전 노드
Node<E> removedNode = prevNode.next; // 삭제할 노드
Node<E> nextNode = removedNode.next; // 삭제할 노드의 다음 노드
E element = removedNode.data; // 삭제되는 노드의 데이터를 반환하기 위한 임시변수
/**
* index == 0 일 때의 조건에서 이미 head노드의 삭제에 대한 분기가 있기 때문에
* prevNode는 항상 존재한다.
*
* 그러나 nextNode의 경우는 null일 수 있기 때문에 (= 마지막 노드를 삭제하려는 경우)
* 이전처럼 반드시 검사를 해준 뒤, nextNode.prev에 접근해야 한다.
*/
prevNode.next = null;
removedNode.next = null;
removedNode.prev = null;
removedNode.data = null;
if(nextNode != null) {
nextNode.prev = null;
nextNode.prev = prevNode;
prevNode.next = nextNode;
}
/**
* nextNode가 null이라는 것은 마지막 노드를 삭제했다는 의미이므로
* prevNode가 tail이 된다. (연결 해줄 것이 없음)
*/
else {
tail = prevNode;
}
size--;
return element;
}
@Override
public boolean remove(Object value) {
Node<E> prevNode = head;
Node<E> x = head; // removedNode
// value 와 일치하는 노드를 찾는다.
for (; x != null; x = x.next) {
if (value.equals(x.data)) {
break;
}
prevNode = x;
}
// 일치하는 요소가 없을 경우 false 반환
if(x == null) {
return false;
}
// 삭제하려는 노드가 head일 경우 remove()로 삭제
if (x.equals(head)) {
remove();
return true;
}
// remove(int index)와 같은 메커니즘으로 삭제
else {
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;
}
}
1) 가장 앞의 요소(head) 삭제(삭제 연산의 기초) - remove()
head가 가리키는 노드의 링크와 데이터를 null로 지워준 뒤 head를 다음 노드로 업데이트 해준다.
삭제하려는 노드가 리스트에서 유일한 노드였을 경우 해당 노드를 삭제하면 tail이 가리키는 노드 또한 없어지게 된다.
2) 특정 index의 요소 삭제 - remove(int index)
삭제하려는 노드의 이전 노드의 next변수를 삭제하려는 노드의 다음 노드를 가리키게 해준다.
총 알아야 할 노드는 3개 = 삭제할 노드, 삭제할 노드의 이전 노드, 삭제할 노드의 다음 노드
[고려해야 할 포인트]
첫번째 요소가 삭제되는 경우나 요소가 한 개 남았을 경우에는 이전에 만들어놓았던 remove()를 호출하면 된다.
요소가 한 개가 남았을 때는 size=1인데 사용자는 index 파라미터로 0만 입력할 수 있기 때문이다.
그 외의 숫자를 입력하면 범위 체크에 걸려 예외를 던진다.
결과적으로 index==0을 검사하는 것은 자연스레 요소가 한 개 남았을 때와 같은 경우가 된다.
이 말은 거꾸로하면 위 조건에 걸리지 않았을 경우에는,
삭제하려는 노드의 앞 노드인 prevNode는 반드시 존재한다는 것이다.
삭제되는 노드가 마지막 노드일 경우도 생각해야 하는데 이때에는 nextNode가 null값인지 확인해주면 된다.
3) 특정 요소 삭제 - remove(Object value)
remove(int index)메소드와 동일한 메커니즘으로 작동한다. 하지만 삭제하려는 요소가 존재하는지를 꼭 염두해두어야한다.
삭제하려는 요소를 찾지못했을 경우 false반환, 찾았을 경우 remove(int index)와 동일한 삭제 방법을 사용한다.
5. get, set, indexOf, contains
@Override
public E get(int index) {
return search(index).data;
}
@Override
public void set(int index, E value) {
Node<E> prev = search(index);
prev.data = null;
prev.data = value;
}
@Override
public int indexOf(Object o) { // 정방향 탐색
int index = 0;
for (Node<E> x = head; x != null; x = x.next) {
if (o.equals(x.data)) {
return index;
}
index++;
}
return -1;
}
public int lastIndexOf(Object o) { // 역방향 탐색
int index = size;
for (Node<E> x = tail; x != null; x = x.prev) {
index--;
if (o.equals(x.data)) {
return index;
}
}
return -1;
}
@Override
public boolean contains(Object item) {
return indexOf(item) >= 0;
}
1) get(int index) :노드의 데이터 반환
2) set(int index, E value) : 기존 index에 위치한 데이터를 새로운 데이터로 교체
3) indexOf(Object value) : 찾고자하는 요소의 위치(index)를 반환 (없을 경우 -1 반환)
4) contains(Object value) : 찾고자하는 요소의 존재여부 반환(true false)
6. size, isEmpty, clear
@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;
}
1) size() : 요소의 개수 반환
2) isEmpty() : 요소가 비어있는지 확인
3) clear() : 모든 요소를 삭제
7. clone
DLinkedList<Integer> original = new DLinkedList<>();
original.add(10); // original에 10추가
DLinkedList<Integer> copy = original;
DLinkedList<Integer> clone = (DLinkedList<Integer>) original.clone();
copy.add(20); // copy에 20추가
clone.add(30); // clone에 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);사용자가 사용하고 있던 LinkedList를 새로 하나 복제하고 싶을 때 쓰는 메소드
얕은 복사(shallow copy) = copy
깊은 복사 = clone
8. toArray
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) {
// Arrya.newInstance(컴포넌트 타입, 생성할 크기)
a = (T[]) java.lang.reflect.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;
}
1) Object[] toArray()
아무런 인자 없이 LinkedList의 객체를 객체배열(Object)로 반환해주는 메소드
LinkedList에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환되는 장점이 있다.
2) T[] toArray(T[] a)
이미 생성된 다른 배열에 LinkedList를 복사해주는 메소드
DLinkedList<Integer> list = new DLinkedList<>();
// get list to array (using toArray())
Object[] array1 = list.toArray();
// get list to array (using toArray(T[] a)
Integer[] array2 = new Integer[10];
array2 = list.toArray(array2);ArrayList와의 배열 생성방식에 차이가 있는데, ArrayList에서는 내부에서 데이터를 Object[] 배열에 담았기때문에 데이터 복사가 쉬웠으나,
LinkedList는 노드라는 객체에 데이터를 담고 있는 연결리스트이기때문에 노드 자체가 Integer, String처럼 래퍼클래스나 사용자정의 데이터를 가질 수 없다.
노드의 data변수가 객체 타입 변수인 것이지 노드 자체가 객체 타입을 갖지는 못한다.
그래서 ArrayList처럼 Arrays.copyOf() 메소드나 System.arraycopy를 쓰기 어렵다.
이럴때 쓰는 것이 lang.reflect 패키지에 있는 Array클래스의 newInstance 메소드이다.
예를 들어 E Type이 Integer이고, T Type이 Object라고 가정해볼때
Object는 Integer보다 상위 타입으로 Object안에 Integer타입의 데이터를 담을 수 있다.
상위 타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성한 것이다.
하위 타입(축소)의 경우 Array클래스에서 예외를 던지기 때문에 이에 대한 별다른 예외를 처리할 필요는 없다.
<파라미터로 주어지는 배열 A가 현재 리스트의 요소보다 작은 경우>
파라미터로 주어지는 배열 A의 타입을 알기 위해 getClass().getComponentType()을 통해 객체가 어떤 유형의 배열인지를 판단하고 배열의 크기를 설정한다.
그런 다음 A를 얕은 복사를 통해 Object[] 배열을 하나 만들어 데이터를 넣어준다음 A를 반환한다.
얕은 복사이기 때문에 result 배열에 담으면 자동으로 A배열에도 영향을 미치는 것을 활용한 방법이다.
<파라미터로 주어지는 배열 A가 현재 리스트의 요소보다 큰 경우>
앞부분부터 array에 있던 요소만 복사해서 A배열에 넣고 반환한다.
9. sort
// Comparator의 구현을 통해 명시적으로 Arrays.sort()에 파라미터로 넘기는 방법
import java.util.Comparator;
public class test {
public static void main(String[] args) {
SLinkedList<Student> list = new SLinkedList<>();
list.add(new Student("김자바", 92));
list.add(new Student("이시플", 72));
list.add(new Student("조시샵", 98));
list.add(new Student("파이손", 51));
list.sort(customComp); // Comparator을 파라미터로 넘겨준다.
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
// 사용자 설정 comparator(비교기)
static Comparator<Student> customComp = new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.score - o1.score;
}
};
}
class Student {
String name;
int score;
Student(String name, int score){
this.name = name;
this.score = score;
}
public String toString() {
return "이름 : " + name + "\t성적 : " + score;
}
}
// Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법
public class test {
public static void main(String[] args) {
SLinkedList<Student> list = new SLinkedList<>();
list.add(new Student("김자바", 92));
list.add(new Student("이시플", 72));
list.add(new Student("조시샵", 98));
list.add(new Student("파이손", 51));
list.sort();
for(int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
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;
}
}ArrayList에서는 내부적으로 Object[] 배열을 사용하기 때문에 Arrays.sort() 메소드를 쓰면 간단하다.
하지만 LinkedList같은 객체 배열의 경우 Collections.sort() 메소드를 사용하게 되는데, 해당 메소드도 내부에서는 Arrays.sort()를 쓴다.
리스트를 Object[] 배열로 반환시켜 Arrays.sort()를 통해 정렬한 후 정렬된 데이터를 다시 리스트의 노드에서 셋팅해준다.
래퍼클래스 타입이라면 따로 Comparator를 구현해주지 않아도 되지만, 사용자 정의 클래스같은 경우에는 사용자가 따로 해당 객체에 Comparable를 구현해주거나 Comparator를 구현해서 파라미터로 넘겨줘야한다.
정렬 메소드를 생성할 때 Comparable이 구현되어있는 파라미터로 Comparator를 넘겨주지않는 경우와 Comparator를 넘겨주어 정의된 정렬 방식을 사용하는 경우를 생각해야한다.
Collections.sort() - Comparator 파라미터가 없는 경우
Collections.sort() - Comparator 파라미터가 있는 경우
List.sort() - List 인터페이스의 default메소드
출처 및 참고
https://st-lab.tistory.com/169
https://prinha.tistory.com/entry/%E3%85%87%E3%85%87
[JAVA 자료구조] Singly LinkedList (단일 연결리스트)
Singly LinkedList 배열이 아닌 '노드'를 이용하여 여러 노드를 하나의 체인처럼 단방향으로 연결한 리스트 (위 그림에서 각각의 레퍼런스 변수는 다음 노드객체를 가리키고 있음) 이미지 출처 : https
prinha.tistory.com
'Programming > Algorithm&DataStructure' 카테고리의 다른 글
| [JAVA/자료구조] Stack 구현 (0) | 2021.08.09 |
|---|---|
| [JAVA/자료구조] Stack Interface (0) | 2021.08.09 |
| [JAVA 자료구조] Singly LinkedList (단일 연결리스트) (0) | 2021.08.05 |
| [JAVA 자료구조] ArrayList (0) | 2021.08.04 |
| [JAVA 자료구조] List Interface (리스트 인터페이스) (0) | 2021.08.04 |
