[JAVA/자료구조]
DoublyLinkedList
더블링크드리스트 코드
및 알아보기
그림으로 알아보기
위와 같은 구조가 더블링크드리스트 ( DoublyLinkedList ) 입니다.
노드와 노드가 서로 연결되어 있다는 점이라는 장점이 있습니다.
단순열결리스트와는 다르게 이전 노드와 다음 노드로 구성되어 있습니다.
단점으로는 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 합니다.
메모리를 더 많이 사용한다는 의미이기도 하죠
왜그런지는
코드를 통해서 알아보도록 하겠습니다.
public class DoblyLinkedList {
private Node head;
private Node tail;
private int size = 0;
private class Node {
private Object data;
private Node next;
private Node prev;
public Node(Object input) {
this.data = input;
this.next = null;
this.prev = null;
}
public String toString() {
return String.valueOf(this.data);
}
}
/**
* 처음 노드 만들기
* @param input 데이터
*/
public void addFirst(Object input) {
Node newNode = new Node(input);
newNode.next = head;
if(head != null) {
head.prev = newNode;
}
head = newNode;
size++;
if(head.next == null) {
tail = head;
}
}
public void addLast(Object input) {
Node newNode = new Node(input);
if(size == 0) {
addFirst(input);
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
size++;
}
}
public void add(int k, Object input) {
if(k == 0) {
addFirst(input);
}else {
Node temp1 = node(k-1);
Node temp2 = temp1.next;
Node newNode = new Node(input);
temp1.next = newNode;
newNode.next = temp2;
if(temp2 != null) {
temp2.prev = newNode;
}
newNode.prev = temp1;
size++;
if(newNode.next == null) {
tail = newNode;
}
}
}
public Object removeFirst() {
Node temp = head;
head = head.next;
Object returnData = temp.data;
temp = null;
if(head != null) {
head.prev = null;
}
size--;
return returnData;
}
public Object remove(int k) {
if(k == 0) {
return removeFirst();
}else {
Node temp = node(k-1);
Node todoDeleted = temp.next;
temp.next = temp.next.next;
if(temp.next !=null) {
temp.next.prev = temp;
}
Object returnData = todoDeleted.data;
if(todoDeleted == tail) {
tail = temp;
}
todoDeleted = null;
size--;
return returnData;
}
}
public Object removeLast() {
return remove(size-1);
}
public int size() {
return size;
}
public Object get(int k) {
Node temp = node(k);
return temp.data;
}
public int indexOf(Object inputdata) {
Node temp = head;
int index = 0;
while(temp.data != inputdata) {
temp = temp.next;
index++;
if(temp == null) {
return -1;
}
}
return index;
}
public ListIterator listIterator() {
return new ListIterator();
}
public String toString() {
if(head == null) {
return "[]";
}
Node temp = head;
String str = "[";
while(temp.next != null) {
str += temp.data + ", ";
temp = temp.next;
}
str += tail.data;
return str+"]";
}
Node node(int index) {
if(index < size/2) {
Node x = head;
for(int i=0; i < index; i++) {
x = x.next;
}
return x;
}else {
Node x = tail;
for (int i = size-1; i>index; i++) {
x=x.prev;
}
return x;
}
}
public class ListIterator{
private Node next;
private Node lastReturned;
private int nextIndex = 0;
ListIterator(){
next = head;
}
public Object next() {
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.data;
}
public boolean hasNext() {
return nextIndex < size();
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public void add(Object input) {
Node newNode = new Node(input);
if(lastReturned == null) {
head = newNode;
newNode.next = next;
}else {
lastReturned.next = newNode;
newNode.prev = lastReturned;
if(next != null) {
newNode.next = next;
next.prev = newNode;
} else {
tail = newNode;
}
}
lastReturned = newNode;
nextIndex++;
size++;
}
public void remove() {
if(nextIndex == 0) {
throw new IllegalStateException();
}
Node n = lastReturned.next;
Node p = lastReturned.prev;
if(p == null) {
head = n;
head.prev = null;
lastReturned = null;
}else {
p.next = next;
lastReturned.prev = null;
}
if(n == null) {
tail = p;
tail.next = null;
}else {
n.prev = p;
}
if(next == null) {
lastReturned = tail;
}else {
lastReturned = next.prev;
}
size--;
nextIndex--;
}
}
}
LinkedList 와 다른것이 이전 노드를 더 저장한다는 것입니다.
설명은 조금씩 추가하도록 하겠습니다.
이상으로 DoublyLinkedList 더블링크드리스트 코드 알아보기
포스팅을 마치겠습니다.
