연결리스트

연결 리스트는 자료를 저장하는 노드들의 주소를 서로 참조하여 연결되어 있는 선형 자료구조처럼 표현하는 자료구조입니다.

연결리스트의 저장방식

각각의 노드들은 자기 자신 다음의 노드를 참조하여 첫 노드에서 계속 다음 노드를 참조하다보면 모든 자료를 선형으로 탐색할 수 있습니다.

이 때 자료가 물리적으로 선형으로 배치된 것이 아닌 논리적인 선형 배치이므로 실제 메모리 주소와 각 자료의 순서는 관련이 없습니다.

연결리스트 특징

배열 구조의 리스트는 배열의 한 자리를 비우고 나머지 원소들을 당겨오기 때문에 많은 작업이 소요되지만, 연결리스트는 각 노드들이 서로 참조를 하는 구조이기에 중간에 위치한 값의 참조값만 변경하게 되면 중간의 삽입 및 삭제가 쉽습니다. (삭제와 삽입 연산만으로는 O(1)의 시간 복잡도)

하지만 배열 자료구조처럼 각 노드를 인덱스 직접 접근할 수 없기 때문에 랜덤액세스에 대한 시간 복잡도가 많이 소요되는 단점이 있습니다.(각 노드의 연결점을 찾아 해당하는 자료 위치까지 이동해야하므로 O(N)의 시간 복잡도)

연결리스트 종류

단일 연결리스트

각 노드는 하나의 참조값과 해당 노드에 저장할 값만을 가지며 참조값은 다음 노드 객체를 가르키고 있습니다.

이전 노드의 참조가 없으므로 첫 노드에서 마지막 노드까지 단방향으로만 연결됩니다.

이중 연결리스트

이중 연결리스트는 이전 노드와 다음 노드의 대한 참조값 및 저장할 값을 갖고 있습니다.

이전 노드의 참조까지 포함하므로 양방향으로 연결됩니다.

원형 연결리스트

원형 연결리스트는 리스트의 마지막 노드의 참조를 첫번째 노드와 연결시켜 순환이 가능한 리스트를 말합니다.

이중 연결 리스트 구현

클래스 정의

이중 연결리스트를 자바에서 직접 구현하려면 리스트에 대한 클래스와 각 노드에 대한 클래스를 정의해야합니다.

public class MkLinkedList <T>{
	//노드 클래스
	private class Node{
		//왼쪽 오른쪽 링크 및 값
		Node leftLink;
		Node rightLink;
		T value;

		//기본생성자
		public Node() {
		}

		//모든 속성 생성자
		public Node(T value, Node leftLink, Node rightLink){
			this.value = value;
			this.leftLink = leftLink;
			this.rightLink = rightLink;
		}
	}

	//리스트의 크기
	private int size;
	//리스트의 헤드 ( 값을 저장하지 않음, 시작 주소)
	private final Node head;
	//리스트의 꼬리
	private Node tail;

	//기본 생성자
	public MkLinkedList(){
		this.head = new Node();
	}

• Node : 각 정점과 연결 참조를 포함한 노드 객체를 이너 클래스로 작성
• size : 리스트 내의 정점 수 값을 저장하는 속성
• head : 실제 값을 저장하지 않는 시작 Node 객체
• tail : 마지막 노드 객체를 참조

리스트의 헤드를 실제 데이터 저장이 없는 객체로 선언하여 시작 위치를 따로 지정하였습니다.

삽입

리스트에 값을 제일 첫 번째에 삽입, 중간에 삽입, 마지막에 삽입하는 메서드를 작성합니다.

첫 번째에 삽입 - addFirst

첫 번째에 삽입하기 위해 객체를 만든 후 그 값을 헤드 속성과 연결해 줍니다. 그리고 헤드와 원래 연결되어 있던 노드의 참조를 새 노드로 합니다.

public void addFirst(T val) {
	System.out.println("머리 추가 : " + val);
	//새 노드 갖기
	Node newNode = new Node(val, head, head.rightLink);
	//만약 리스트의 tail 이없다면, 즉 첫번째 노드라면
	if (head.rightLink == null) {
		//꼬리만 붙이기
		tail = newNode;
	}
	//아닐 경우
	else {
		//헤드의 오른쪽 노드의 왼쪽링크에 새 노드 연결하기
		head.rightLink.leftLink = newNode;
	}
	//헤드의 오른쪽 링크에 새 노드 연결하기
	head.rightLink = newNode;
	//사이즈 늘리기
	size++;
}

만약 첫번째로 삽입되는 노드라면 꼬리 값으로 해당 노드를 설정해줍니다.

마지막 삽입 - addLast

//꼬리에 추가하기
public void addLast(T val){
	System.out.println("꼬리 추가 : " + val);
	//기존의 꼬리가 없다면 ( 첫 노드일 경우, size==0 )
	if (tail == null) {
		addFirst(val);
		return;
	}

	//꼬리를 왼쪽 링크로 갖는 새 노드 추가
	Node newNode = new Node(val, tail, null);
	//현재 꼬리 노드의 오른쪽 노드를 새 노드로 설정
	tail.rightLink = newNode;
	// 꼬리 노드를 현재 노드로 설정
	tail = newNode;
	size++;
}

만약 첫번쨰로 삽입하는 노드라면 첫 번째 노드 삽입을 호출합니다.

중간 삽입 - add

삽입할 자료의 인덱스를 매개변수로 받아서 추가합니다.

//인덱스에 맞는 값 추가하기
public void add(int index, T val) {
	System.out.println("허리에 추가 ! : " + val);
	//인덱스에 해당하는 노드 가져오기
	Node temp = getNode(index);
	//인덱스에 해당하는 노드가 없다면(범위 초과 등) 꼬리에 추가
	if (temp == null) {
		addLast(val);
		return;
	}
	//인덱스에 해당하는 노드의 왼쪽 링크를 새 노드의 왼쪽 링크로 연결, 오른쪽 링크를 인덱스에 해당하는 노드로 설정
	Node newNode = new Node(val, temp.leftLink, temp);
	//인덱스에 해당하는 노드의 왼쪽 노드의 오른쪽 링크를 현재 노드로 설정
	temp.leftLink.rightLink = newNode;
	//인덱스의 왼쪽 링크를 새 노드로 설정
	temp.leftLink = newNode;
	size++;
}

getNode 메서드로 현재 넣고자하는 인덱스에 해당하는 노드의 참조를 가져옵니다.

해당 노드가 존재하지 않는다면 addLast 로 맨 마지막에 추가해줍니다.

값 뽑기

참조 값 뽑기

인덱스를 입력으로 받아 인덱스에 해당하는 노드의 레퍼런스를 반환시킵니다.

//인덱스에 해당하는 노드 가져오기
private Node getNode(int index) {
	//범위 초과 및 음수 입력이면 null 반환
	if(index < 0 || index >= size)   return null;
	//첫번째 노드부터 인덱스만큼 이동
	Node temp = head.rightLink;
	for (int i = 0; i < index; i++) {
		temp = temp.rightLink;
	}
	//찾은 노드 반환
	return temp;
}

올바르지 않은 인덱스(리스트 크기 초과, 음수 인덱스 입력) 시 null 을 반환합니다.

클래스 내부에서만 동작할 것이므로 private 키워드를 작성합니다.

실제값 뽑기

인덱스 입력에 해당하는 실제값을 뽑습니다.

//인덱스에 해당하는 값 반환
public T get(int index) {
	Node temp = this.getNode(index);
	//찾은 노드가 null 이라면 null, 아니라면 value 반환
	return temp == null ? null : temp.value;
}

삭제

자바에서는 GC 에 의해 참조가 없는 객체의 메모리 제거가 되므로 직접 메모리를 해제하는 과정은 작성하지 않습니다.

이 때 삭제될 노드의 참조를 지워주지 않는다면 다른 노드에 대한 참조가 계속 존재하므로 문제가 발생할 수 있으니, 삭제할 노드의 참조도 모두 지워줍니다.

첫 번째 노드 삭제

public T removeFirst() {
	//노드가 하나도 없다면 반환
	if(head.rightLink == null)  return null;
	size--;

	//삭제할 노드 타겟
	Node target = head.rightLink;

	//헤드와 새로 연결해야할 노드 temp 설정
	Node temp = target.rightLink;
	//삭제할 노드의 왼쪽 링크를 끊음
	target.leftLink = null;

	//새로 연결할 노드가 없는 경우( 사이즈가 1)
	if (temp == null) {
		head.rightLink = null;
		// 그 경우 삭제할 노드가 tail 이므로 tail = null 설정
		tail = null;
		return target.value;
	}
	//삭제할 노드의 오른쪽 링크를 제거
	target.rightLink = null;
	//새로 연결할 노드의 left를 각각 헤드와 연결
	temp.leftLink = head;
	head.rightLink = temp;
	return target.value;
}

노드가 하나도 없거나, 하나만 있는 경우의 예외처리를 따로 진행합니다.

반환값으로는 제거한 노드의 값을 갖습니다.

마지막 노드 삭제

//꼬리 지우기
	public T removeLast() {
		//꼬리가 없다면, 즉 아무것도 없다면
		if(tail == null)    return null;
		size--;
		//꼬리 노드를 타겟으로 설정
		Node target = tail;
		//꼬리를 타겟의 왼쪽(현재 꼬리 이전 노드)으로 설정
		tail = target.leftLink;
		//타겟의 왼쪽 연결을 끊음
		target.leftLink = null;
		//새로운 꼬리의 오른쪽 연결을 끊음
		tail.rightLink = null;
		return target.value;
	}

노드가 없는 경우의 예외처리를 해줍니다.

중간 노드 삭제

//인덱스 값에 맞는 노드 지우기
public T remove(int index) {
	//인덱스 찾기
	Node target = this.getNode(index);
	//해당하는 인덱스가 없을 경우(범위초과 등) 리턴
	if (target == null)    return null;
	System.out.println("지우기 : " + index);
	size--;
	//꼬리가 아니라면 타겟을 지정하는 오른쪽 링크를 끊고, 타겟이전의 노드와 연결
	if (target != tail) {
		target.rightLink.leftLink = target.leftLink;
	} else {
		//꼬리라면, 꼬리 값 새로 지정
		tail = target.leftLink;
	}
	//타겟의 왼쪽 노드의 링크를 타겟의 오른쪽 노드로 설정
	target.leftLink.rightLink = target.rightLink;

	//타겟의 연결 끊기
	target.leftLink = null;
	target.rightLink = null;

	return target.value;
}

getNode 메서드로 삭제할 노드를 찾아 그 노드의 연결을 해제합니다.

기타 메서드

링크드 리스트의 size() 메서드 및 isEmpty() , clear() 메서드를 구현합니다.

또한 스택 및 큐로 사용할 수 있도록 해당하는 메서드도 작성합니다.

//스택 push
public void push(T val) {
	this.addFirst(val);
}
//스택 pop
public T pop() {
	return this.removeFirst();
}

//큐 peek
public T peek() {
	return this.get(0);
}

//큐 poll
public T poll() {
	return this.removeFirst();
}

//큐 offer
public void offer(T val) {
	this.addLast(val);
}

//모든 노드 지우기
public void clear() {
	while (size != 0) {
		removeLast();
	}
}

//사이즈 비우기
public int size() {
	return size;
}

//노드가 비었는지 검사하기
public boolean isEmpty() {
	return size == 0;
}