연결 리스트(linked list)

1. 개념정리

1) 같은 타입인 여러 개의 변수를 하나로 묶어놓은 것

- 타입은 기본형, 참조형 가리지 않는다.

- 물리적으로(하드디스크) 연속되지 않은 공간에 있어도 상관없다..

- java.util 패키지에 LinkedList 클래스가 있다.

2) 리스트의 요소를 노드(node)라고 부르며, 각 노드에는 값(value)과 다음 노드의 주소가 저장된 링크(next)가 있다.

- 특히, 맨 앞 노드를 head, 맨 뒤 노드를 tail이라고 부른다.

- 마지막 노드라면 next == null

- 데이터가 추가되면 연결만 해주면 되기 때문에, 연결 리스트의 최대 크기는 정해져 있지 않다.

3) 이중 연결 리스트는 단순 연결 리스트에서 이전 노드의 주소가 저장된 링크(previous)가 추가된 것이다.

- 맨 처음 노드의 previous == null

- 맨 마지막 노드의 next == null

4) 원형 연결 리스트는 이중 연결 리스트의 맨 앞과 맨 뒤를 연결해 준 리스트다.

 

2. 구현 코드

class LLNode { // 문자열을 담은 연결 리스트 노드 클래스
	private String info; // 노드에 담긴 문자열
	private LLNode next; // 다음 노드를 담은 링크
	
	LLNode(String info){ // 생성자
		this.info = info;
		next = null;
	}
	
	public void setInfo(String info) { this.info = info; } // 노드의 문자열 설정
	
	public String getInfo()	{ return info; } // 노드의 문자열 반환
	
	public void setNext(LLNode next) { this.next = next; } // 노드의 다음 링크 설정
	
	public LLNode getNext(){ return next; } // 노드의 다음 링크 반환
}

- 이중 연결 리스트에는 링크로 previous를 추가하고 head.previous == null, tail.next == null로 하면 된다.

- 원형 연결 리스트에는 링크로 previous를 추가하고 head.previous == tail, tail.next == head로 하면 된다.

 

3. 예제 코드

// 1) 노드 생성
LLNode n1 = new LLNode("muzi");
LLNode n2 = new LLNode("choonsik");
LLNode n3 = new LLNode("tube");
n1.setNext(n2);
n2.setNext(n3); 

// 연결 순서: n1 -> n2 -> n3
LLNode head = n1;
LLNode tail = n3;


// 2) 추가

// 2)-1. 맨 뒤에 추가하기
LLNode n4 = new LLNode("con");
n3.setNext(n4); // n1 -> n2 -> n3 -> n4
tail = n4;

// 2)-2. 중간에 추가하기
// n2 뒤에 n5 끼워넣기
LLNode n5 = new LLNode("neo");		
n5.setNext(n2.getNext()); // n5.next == n2.next
n2.setNext(n5); // n1 -> n2 -> n5 -> n3 -> n4

// 2)-3. 맨 앞에 추가하기
LLNode n6 = new LLNode("freinds");		
n6.setNext(head); // n6 -> n1 -> n2 -> n5 -> n3 -> n4
head = n6;


// 3) 탐색 & 수정

// "choonsik"을 찾아 "춘식"으로 바꾸기
LLNode n = head;
while(n!=null) { 
    if(n.getInfo().equals("choonsik")) {
        n.setInfo("춘식");
        break;
    }
    n = n.getNext();
}


// 4) 삭제

// 4)-1. 맨 앞 노드 삭제하기
head = head.getNext(); // n1 -> n2 -> n5 -> n3 -> n4
// 사용되지 않는 n6는 가비지 컬렉터에 의해 삭제된다.

// 4)-2. 맨 뒤 노드 삭제하기
n = head;
while(n!=null) {
    if(n.getNext().getNext()==null) {
        n.setNext(null);
        tail = n;
        break;
    }
    n = n.getNext();
} // n1 -> n2 -> n5 -> n3

// 실제로 잘 작동했는지 확인해보기
n = head;
while(n!=null) {
    System.out.println(n.getInfo());
    n = n.getNext();
}
// 출력 결과
muzi
춘식
neo
tube