[JAVA #19] 연결 리스트(LinkedList) 구현하기

💡연결 리스트의 특징💡

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
• 연결 리스트의 i 번째 요소를 찾는게 걸리는 시간은 요소의 개수에 비례 : O(n)
• jdk 클래스 : LinkedList
• head가 첫 번째 요소가 되고 다음 요소는 이 요소를 가리킴

private MyListNode head;
    int count;

리스트가 비어있을 경우(첫 요소)

• head에 요소를 넣음

MyListNode newNode;
        if(head == null){  //맨 처음일때
            newNode = new MyListNode(data);
            head = newNode;
        }

리스트가 비어있지 않을 경우, 맨 마지막에 요소를 넣고자 하는 경우(add)

• next가 null인 마지막 요소까지 간 다음 새 노드를 마지막 요소의 next로 연결한다

else{
            newNode = new MyListNode(data);
            MyListNode temp = head;
            while(temp.next != null)  //next가 null인 곳(맨 뒤)으로 가서
                temp = temp.next;
            temp.next = newNode; //next를 새 노드로 연결	
        }
        count++;
        return newNode; 

리스트 중간에 요소를 넣고자 하는 경우 (insert)

1. 넣고자 하는 인덱스가 가능한 범위 내에 있는지 확인 후 에러

if(position < 0 || position > count ){
            System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
            return null;
        }

2. 맨 앞에 넣을 경우 새 노드가 head가 되어야 한다, 원래 head였던 노드는 새 노드의 next로

 if(position == 0){  //맨 앞으로 들어가는 경우
            newNode.next = head;
            head = newNode;
        }

3. 중간에 넣을 경우 head부터 인덱스까지 계속 연결해서 앞 노드를 찾는다

else{
     MyListNode preNode = null;
     for(i=0; i<position; i++){
     	preNode = tempNode; //처음 tempNode는 head
     	tempNode = tempNode.next;
     }
     newNode.next = preNode.next; // 앞 노드의 next 였던 노드를 새 노드의 next로 지정
     preNode.next = newNode; //앞 노드의 next를 새 노드로 지정
        }
        count++;
        return newNode;

리스트에 요소를 삭제하고자 하는 경우 (remove)

1. 삭제하고자 하는 인덱스가 가능한 범위 내에 있는지 확인 후 에러

if(position >= count ){
            System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
            return null;
        }

2. 맨 앞의 요소를 삭제하고자 하는 경우

if(position == 0){  //맨 앞을 삭제하는 경우 head 노드를 head노드의 next로 바꿔주면 됨
	head = tempNode.next;
}

3. 중간의 요소를 삭제하고자 하는 경우

else{
	MyListNode preNode = null;
    for(i=0; i<position; i++){	//삭제하고자 하는 노드의 앞 노드를 찾는다
    	preNode = tempNode;
        tempNode = tempNode.next; //지우려는 노드가 temp 노드
    }
    preNode.next = tempNode.next; //앞 노드의 next를 삭제하고자 하는 노드의 next로 바꾼다
}
count--;
System.out.println(position + "번째 항목 삭제되었습니다.");
return tempNode;