Linked List(연결 리스트)
중요한 자료구조들에 대한 ADT(Abstract Data Type)에 대해서는 알고 있다.
하지만 주로 파이썬으로 구현해보았기 때문에 이번에 자바로 구현해보면서 비교해보는 것도 좋은 공부가 될 거라고 생각한다.
연결리스트 구현
public class MyLinkedList {
private MyListNode head;
int count;
public MyLinkedList(){
this.head = null;
this.count = 0;
}
public void addElement(String data){
if (head == null){
MyListNode newNode = new MyListNode(data);
head = newNode;
}
else{
MyListNode newNode = new MyListNode(data);
//혹시 모르니까 맨 끝으로 이동
MyListNode tmp = head;
while(tmp.next != null){
tmp = tmp.next;
}
tmp.next = newNode;
}
count++;
}
public void insertElement(int position, String data){
MyListNode tmp = head;
MyListNode newNode = new MyListNode(data);
if(position < 0 || position > count){
System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
}
if(position == 0){
newNode.next = head;
head = newNode;
}
else{
MyListNode preNode = null;
for(int i=0; i<position; i++){
preNode = tmp;
tmp = tmp.next;
}
newNode.next = preNode.next;
preNode.next = newNode;
}
count++;
}
public void removeElement(int position) {
MyListNode tempNode = head;
if(position >= count ){
System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
}
if(position == 0){ //맨 앞을 삭제하는
head = tempNode.next;
}
else{
MyListNode preNode = null;
for(int i=0; i<position; i++){
preNode = tempNode;
tempNode = tempNode.next;
}
preNode.next = tempNode.next;
}
count--;
System.out.println(position + "번째 항목 삭제되었습니다.");
}
public void printAll()
{
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
MyListNode temp = head;
while(temp != null){
System.out.print(temp.getData());
temp = temp.next;
if(temp!=null){
System.out.print("->");
}
}
System.out.println("");
}
}
class MyListNode{
private String data;
public MyListNode next;
public MyListNode(){
this.data = null;
this.next = null;
}
public MyListNode(String data){
this.data = data;
this.next = null;
}
public MyListNode(String data, MyListNode next){
this.data = data;
this.next = next;
}
public String getData(){
return data;
}
}테스트 코드
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addElement("A");
list.addElement("B");
list.addElement("C");
list.printAll();//A->B->C
list.insertElement(3, "D");
list.printAll();//A->B->C->D
list.removeElement(0);//0번째 항목 삭제되었습니다.
list.printAll();//B->C->D
list.removeElement(1);//1번째 항목 삭제되었습니다.
list.printAll();//B->D
}
}Generic(제네릭)
제네릭에 대해서 예전에 배운 적이 있지만, 배운 지 오래돼서 잘 기억나지 않기 때문에 다시 한번 정리해보았다.
제네릭이란?
여러 종류의 데이터 타입을 다룰 수 있도록 데이터 타입을 일반화하는 것을 의미한다.
예를 들어서 Integer이라는 클래스와 Float이라는 클래스가 있다고 생각해보자.
이런 데이터 타입을 지원하는 자료구조를 만들어서 사용하고 싶다면 제네릭을 활용하면 된다.
public class GenericExample {
public static void main(String[] args) {
Number<Integer> int1 = new Number<Integer>();
Number<Float> float1 = new Number<Float>();
}
}
class Number<T>{
private T t;
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}여기서 Number는 T타입을 받아서 컴파일 시 타입을 결정하여 사용한다.
이렇게 하나의 클래스만으로 여러 타입을 처리할 수 있는 객체들을 처리할 수 있게 되었다.
또 제네릭은 타입을 명시함으로써 타입 변환 및 타입 검사에 들어가는 노력을 줄여 객체 타입 안정성을 높일 수 있다는 장점도 가지고 있다.
제네릭 메서드
제네릭은 메서드로도 사용 가능하다.
class Number<T extends Number>{
private T t;
public static <T> T genericMethod(T t){
return t;
}
}조금 특이한 점이 <T> T genericMethod(T t)처럼 같이 메서드 앞에 를 붙인다는 점이다.
를 붙이는 이유는 메서드가 제네릭임을 나타내고, 특히 정적 메서드를 선언시 타입이 필요하기 때문이다.
다음의 예제를 한번 살펴보자.
class GenericClass<T> {
public static void method1(T t) {
}
}
class GeneralClass {
public static <T> void method2(T t) {
}
}이 두 메서드 중 오류가 발생하는 쪽은 어느 쪽일까?
정답은 method1이다.
그 이유는 정적(static) 메서드이기 때문이다.
정적(static)이란 static이 포함된 변수나 메서드들을 의미하는데, 이렇게 static이 붙어있는 변수나 메서드들은 컴파일 시 메모리 영역에 바로 로딩된다.
제네릭 메서드도 마찬가지로 정적 메서드로 활용할 때, 미리 메모리에 올라가면서 구체적인 타입을 필요로 하기 때문에 제네릭 메서드 앞의 <T>를 통해 타입을 제공받는다.
제네릭과 와일드 카드
와일드 카드에 대해서 알아보기 전에 아래의 예제를 살펴보자.
//1. General Method
public static void peekBox(Box<Object> box) {
System.out.println(box);
}
//2. Generic Method
public static <T> void peekBox(Box<T> box) {
System.out.println(box);
}이 두 메서드는 Box타입의 어떤 타입이든 잘 작동할 것처럼 보인다.
하지만 첫번째 메서드에서 Box을 인자로 넘기면 오류가 발생한다.
Box와 Box에서 Box이 Box를 상속한다고 생각할 수도 있지만
실제로 Box와 Box은 완전히 별개의 타입이고 상속은 이뤄지지 않는다.
따라서 제네릭에서 상속을 확인하기 위해서는
- 클래스 간의 상속을 확인한다.
- 같은 타입이어야 한다.
이번에는 와일드 카드를 사용한 예제를 살펴보자.
//1. Generic Method
public static <T> void peekBox(Box<T> box) {
System.out.println(box);
}
//2. Wildcard가 파라미터인 Method
public static void peekBox(Box<?> box) {
System.out.println(box);
}위의 코드는 둘 다 잘 작동한다.
여기서 <?>는 와일드 카드를 의미하는데, 제네릭과 굉장히 유사해보이지만 둘은 다른 성질을 가지고 있다.
List<?> list;
// 1. 원소를 꺼내 와서는 Object에 정의되어 있는 기능만 사용하겠다. equals(), toString(), hashCode()…
// 2. List에 타입이 뭐가 오든 상관 없다. 나는 List 인터페이스에 정의되어 있는 기능만 사용하겠다. size(), clear().. 단, 타입 파라미터와 결부된 기능은 사용하지 않겠다! add(), addAll()
List<T> list;
// 1. 원소를 꺼내 와서는 Object에 정의되어 있는 기능만 사용하겠다. equals(), toString(), hashCode()…
// 2. List에 타입이 뭐가 오든 상관 없다. 나는 List 인터페이스에 정의되어 있는 기능만 사용을 하고, 타입 파라미터와 결부된 기능도 사용하겠다.즉, 제네릭의 경우 <T>는 특정 타입으로 지정이 되지만, 와일드 카드의 경우 <?>는 타입이 지정되지 않는다.
아래의 예제를 보면 좀더 이해가 쉽다.
public void sampleCode2() {
List<Integer> integerList = Arrays.asList(1, 2, 3);
printList1(integerList);
printList2(integerList);
}
static void printList1(List<?> list) {
// 1. 와일드 카드는 list에 담긴 원소에는 전혀 관심이 없기 때문에 원소와 관련된 add 메소드를 사용할 수 없다.
// 2. 단, null은 들어갈 수 있다.
list.add(list.get(1)); // 컴파일 실패
}
static <T> void printList2(List<T> list) {
// 1. 제네릭은 list에 담긴 원소에 관심을 갖기 때문에 원소와 관련된 add 메소드를 사용할 수 있다.
// 2. 당연히 null도 들어갈 수 있다.
list.add(list.get(1)); // 컴파일 성공
}Challenging(학습하며 어려웠던 점)
제네릭에 대한 개념이 희미해서 다시 한번 쭉 정리해보려고 했는데, 시간이 이렇게 많이 걸릴 줄 몰랐다. 거의 하루종일
제네릭 자체도 까다로운 개념인데, 관련된 개념들이 복잡해서 이해하기 어려웠다.
실제로 제네릭을 설명하기 위해 글을 적기 시작하자 헷갈리는 부분들이 너무 많았다.
그래도 다행히 좋은 포스팅을 발견해서 많은 도움을 받을 수 있었다.
항상 느끼는 거지만 눈으로 보면서 이해하는 것과 글로 적어가면서 설명해보는 것의 차이는 너무 큰 것 같다.
어느 정도 풀어서 설명하듯 글을 적으면 고구마 넝쿨처럼 딸려 있는 지식들을 전부 이해해야 하기 때문인 것 같다.
Resource Links
