[JAVA 자료구조 LinkedList] 만들기 실습 (JAVA 자료구조 연결리스트 만들기 실습)

안녕하세요 ~!

java로 연결리스트를 만들어 보았습니다.

먼저 메소드 정의 부분은 다음과 같습니다.

public interface MyLinkedList<E> {

public int size(); // 데이터 개수 구하기

public void addFirst(E e); // 첫번째 위치에 데이터 추가

public boolean add(E e); // 마지막 위치에 데이터 추가

public boolean add(int index, E e); // 특정 위치에 데이터 추가

public boolean remove(E e); // 데이터 삭제

public E remove(int index); // 데이터 삭제

public E removeFirst(); // 처음 데이터 삭제

public E removeLast();// 마지막 데이터 삭제

public void clear();// 모든 데이터 삭제

public E get(int index); // 특정 인덱스의 데이터 반환

public int indexOf(E e); // 데이터의 인덱스 반환

public E set(int index, E e); // 특정 인덱스의 데이터 수정

public MyIterator<E> iterator(); // 반복자

}

구현부분은 아래와 같습니다 ~!

public class MyLinkedListImpl<E> implements MyLinkedList<E>{

private Node<E> head;

private Node<E> tail;

private int size = 0;

private class Node<T> {

private T data; // 데이터

private Node<T> next; // 다음 데이터의 주소

public Node(T e) {

this.data = e;

this.next = null;

}

}

private Node<E> node(int index) {

if(index<0 || index>size)

return null;

Node<E> node = head;

for(int i=0; i<index; i++) {

node = node.next;

}

return node;

}

@Override

public int size() {

return size;

}

@Override

public void addFirst(E e) {

Node<E> node = new Node<>(e);

if(size==0) {

head = tail = node;

tail.next = null;

} else {

node.next = head;

head = node;

}

size++;

}

@Override

public boolean add(E e) {

if(size==0) {

addFirst(e);

} else {

Node<E> node = new Node<>(e);

tail.next = node;

tail = node;

size ++;

}

return true;

}

@Override

public boolean add(int index, E e) {

if(index < 0 || index > size)

throw new ArrayIndexOutOfBoundsException("size:"+size+", index="+index);

if(index==0) {

addFirst(e);

} else {

Node<E> t1 = node(index-1);

Node<E> t2 = t1.next;

Node<E> newNode = new Node<>(e);

t1.next = newNode;

newNode.next = t2;

size++;

if(newNode.next==null) {

tail = newNode;

}

}

return true;

}

@Override

public boolean remove(E e) {

Node<E> node = head;

Node<E> before = null;

while(node != null) {

if(node.data.equals(e)) { // 만약 삭제할데이터라면 실행.

if(node == head) {

head = node.next;

if(head == null) {

head = tail = null;

}

} else {

before.next = node.next;

if(before.next == null) {

tail = before;

}

}

size--;

node = null;

return true;

}

before = node;

node = node.next;

}

return false;

}

@Override

public E remove(int index) {

if(index >= size)

throw new ArrayIndexOutOfBoundsException("size:"+size+", index="+index);

Node<E> node = node(index);

if(node == null)

return null;

E e = node.data;

if(remove(e)) {

return e;

}

return null;

}

@Override

public E removeFirst() {

return remove(0);

}

@Override

public E removeLast() {

return remove(size-1);

}

@Override

public void clear() {

Node<E> t1=head;

Node<E> t2;

while(t1 != null) {

t2 = t1.next;

t1 = null;

t1 = t2;

}

head = tail = null;

size = 0;

}

@Override

public E get(int index) {

if(index >= size)

throw new ArrayIndexOutOfBoundsException("size:"+size+", index="+index);

Node<E> node = node(index);

return node.data;

}

@Override

public int indexOf(E e) {

Node<E> node = head;

int index = 0;

while(node.data != e) {

node = node.next;

index++;

if(node ==null) {

return -1;

}

}

return index;

}

@Override

public E set(int index, E e) {

if(index >= size)

throw new ArrayIndexOutOfBoundsException("size:"+size+", index="+index);

Node<E> node = node(index);

E oldNode = node.data;

node.data = e;

return oldNode;

}

@Override

public MyIterator<E> iterator() {

return new MyIteratorImpl();

}

private class MyIteratorImpl implements MyIterator<E> {

private Node<E> lastReturned;

private Node<E> next;

private int nextIndex;

public MyIteratorImpl() {

next = head;

nextIndex = 0;

}

@Override

public boolean hasNext() {

return nextIndex < size();

}

@Override

public E next() {

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.data;

}

@Override

public void remove() {

if(nextIndex==0)

throw new IllegalStateException();

MyLinkedListImpl.this.remove(nextIndex-1);

nextIndex--;

}

}

}