자바로 구현한 단일연결리스트
SingleLinkedList.java
//단일 연결리스트를 구현한 클래스
public class SingleLinkedList<E> {
//노드 정보를 저장하는 클래스
private class Node<T> {
private T data; //데이터 필드
private Node<T> next; //주소 필드(다음 노드를 가리킴)
//데이터를 인수로 받아 노드 객체를 생성하는 생성자
public Node(T data) {
this.data = data;
this.next = null;
}
//데이터를 문자열로 반환하는 메서드
@Override
public String toString() {
return String.valueOf(data);
}
}
private Node<E> head = null; //헤드 노드, 맨처음 노드를 찾기 위해 반드시 필요
private int size = 0; //노드의 수를 저장
private Node<E> tail = null; //가장 마지막 노드를 저장하는 변수, 성능을 높일 수 있다.
//노드의 엘리먼트를 []와 콤마로 분리해서 문자열로 반환하는 메서드
//연결리스트의 엘리먼트를 출력하기 위해
public String toString() {
if(head == null){
return "[]";
}
Node<E> temp = head; //temp 변수를 두는 이유는? head 정보를 잃지 않기 위해
String str = "[";
while(temp.next != null){
str += temp.data + ",";
temp = temp.next;
}
str += temp.data;
return str+"]";
}
//전용 메서드, add(E), add(int,E) 메서드에서 사용
//맨 앞에 노드를 추가
private void addFirst(E input){
Node<E> newNode = new Node<>(input);
newNode.next = head; //삭제하면 안됨, add(0, E)할 때 필요
head = newNode;
size++;
if(head.next == null){ //새로 추가된 노드가 가장 마지막 노드이다.
tail = head; //tail = newNode와 동일
}
}
//가장 마지막에 노드를 추가, 전용 메서드
private void addLast(E input){
Node<E> newNode = new Node<>(input);
if(size == 0){
addFirst(input);
} else {
tail.next = newNode; //가장 마지막 노드가 가리키는 노드는 새로 추가되는 노드임
tail = newNode; //새로 추가된 노드가 가장 마지막 노드가 되어야 함
size++;
}
}
//공용메서드, 사용자의 편의를 위해서 제공
public void add(E input){
addLast(input);
}
//주어진 위치에 엘리먼트를 삽입, index 위치에
//index위치의 전(Previous)노드를 찾아야 함
public void add(int index, E input){
if(index == 0){
addFirst(input); //인덱스가 0이면 맨 앞에
} else if(index == size) {
addLast(input); //인덱스가 size이면 맨 마지막 노드 뒤에
} else if(index > size || index < 0) { //인덱스 범위를 넘어서면
throw new IndexOutOfBoundsException(String.valueOf(index)); //예외를 발생시킴
//RuntimeException의 하위 예외, throws 없어도 됨,but 인데스가 범위를 벗어나면 예외 발생
//add(int, E)를 호출하는 곳에서 try~catch블록으로 예외 처리 해 줄것을 권장.
} else {
Node<E> prev = head;
//추가하려는 노드의 전전 노드를 알면 전전노드.next를 전노드에 할당
for (int i=0; i<index-1; i++) {
prev = prev.next;
}
Node<E> newNode = new Node<>(input);
newNode.next = prev.next; // 1
prev.next = newNode; // 2
size++;
// if(newNode.next == null){ //가장 마지막 노드일 경우
// tail = newNode;
// }
}
}// main에서 list.add(2, "F");로 테스트 해 보세요.
//가장 처음 노드를 삭제, head가 처음노드.next를 가리키도록 해야 함
//삭제할 경우는 삭제하는 노드의 값을 반환.
public E removeFirst(){
Node<E> temp = head;
head = temp.next;
E data = temp.data;
temp = null;
size--;
return data;
}
// public void removeFirst() {} //안됨, 리턴타입만 다르게 중복 정의 안됨
//인덱스를 이용해 노드를 삭제
public E remove(int index){
if(index == 0) {
return removeFirst();
}else if(index >= size || index < 0) {
//인덱스가 범위를 넘어서면 예외를 발생시킴
throw new IndexOutOfBoundsException(String.valueOf(index));
}
Node<E> prev = head;
for (int i=0; i<index-1; i++) {// 삭제하려는 노드의 전노드를 찾음
prev = prev.next;
}
Node<E> todoDeleted = prev.next;//별도의 변수로 저장하는 이유는? null을 할당해서 소멸시키기 위해
prev.next = prev.next.next; //prev.next = todoDeleted.next;와 동일
E returnData = todoDeleted.data;
if(todoDeleted == tail){
tail = prev;
}
todoDeleted = null; //null을 할당해서 소멸시킴(GC Thread에의 Garbage Connection 대상)
size--;
return returnData;
}
//인덱스로 데이터를 조회
public E get(int index){
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException(String.valueOf(index));
}
Node<E> temp = head;
for (int i=0; i<index; i++) { //인덱스 위치의 노드를 찾아야 함
temp = temp.next;
}
return temp.data;
}
//노드의 수를 반환하는 메서드
public int size() {
return size;
}
//데이터를 이용해 인덱스를 찾는 메서드
public int indexOf(E data){
Node<E> temp = head;
int index = 0;
//객체는 ==연산자와 equals()에 의해 동등 비교
//주소가 다르면 내용이 다른지도 확인해야 합니다.
while( (temp.data != data) && (!temp.data.equals(data)) ){
temp = temp.next;
index++;
if(temp == null) {
return -1;
}
}
return index;
}
//연결리스트의 내용을 배열로 반환하는 메서드
public Object[] toArray() {
Object[] listArray = new Object[size];
for(int i=0; i<size; i++) {
listArray[i] = get(i);
}
return listArray;
}
//지정한 유형 배열로 반환하는 메서드
//사용법 : String[] listArr = list.toArray(new String[list.size()]);
public E[] toArray(E[] e) {
E[] listArray = e;
for(int i=0; i<size; i++) {
listArray[i] = get(i);
}
return listArray;
}
//연결리스트를 테스하기 위한 코드
public static void main(String[] args) {
//String을 데이터로 갖는 연결리스트 객체 생성
//publci class SingleLinkedList<E> { ... }
//String 데이터만 리스트에 add()할 수 있음
SingleLinkedList<String> list = new SingleLinkedList<String>();
System.out.println(list); //[]
list.add("A"); System.out.println(list); //[A]
list.add("B");
list.add("D"); System.out.println(list); //[A,B,D]
list.add(2, "F"); System.out.println(list); //[A,B,F,D]
list.removeFirst(); System.out.println(list); //[B,F,D]
list.remove(1); System.out.println(list); //[B,D]
list.add("C");
list.add("E"); System.out.println(list); //[B,D,C,E]
System.out.println(list.get(0)); //B
System.out.println(list.get(1)); //D
System.out.println(list.get(2)); //C
System.out.println(list.get(3)); //E
System.out.println(list.indexOf("A")); //-1
System.out.println(list.indexOf("C")); //2
System.out.println(list.indexOf(new String("C"))); //2
String[] strArray = list.toArray(new String[list.size]);
for(String data : strArray) {
System.out.print(data + " ");
}//B D C E
System.out.println();
}
}
|