[자료구조] 연결 리스트(Linked List) 개념과 구현

연결 리스트

선형 리스트는 논리적인 순서와 물리적인 순서가 같기 때문에 원소의 위치를 찾아 접근하기 쉽다는 장점이 있지만, 삽입이나 삭제 연산 후에 논리적인 순서와 물리적인 순서를 유지하기 위해 원소들을 이동시키는 추가적인 작업과 시간이 필요합니다.

 

따라서 원소의 개수가 많고 삽입 · 삭제 연산이 많이 발생하는 경우 원소들의 이동 작업으로 인한 오버헤드가 증가하여 성능상에 문제를 일으킬 수 있습니다. 또한 배열을 이용하여 구현하기 때문에 크기가 제한되고 메모리 사용의 비효율성 문제를 갖고 있습니다.

 

이러한 선형 리스트에서 추가적인 오버헤드 문제와 저장 공간에 대한 문제를 개선한 자료 표현 방식이 연결 리스트(Linked List)입니다. 연결 리스트는 연속한 메모리 물리주소에 원소의 순서를 표현하는 것이 아니라, 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해 연결되는 방식입니다.

노드(Node)

연결 리스트의 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에 <원소, 주소>의 단위로 저장해야 합니다. 이러한 단위구조를 노드라고 합니다.

 

노드

노드는 원소의 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 구성됩니다. 데이터 필드는 저장할 원소의 형태에 따라서 하나 이상의 필드로 구성하기도 하고 링크 필드는 메모리 참조 변수를 사용하여 주소에 대한 참조 값을 저장합니다.

연결 리스트 종류

· 단순 연결 리스트(Singly Linked List)

노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 갖는 연결 리스트입니다.

 

단순 연결 리스트

· 원형 연결 리스트(Cicular Linked List)

단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트입니다. 따라서 마지막 노드와 첫 번째 노드가 연결되어 있기 때문에 링크를 따라 순회하면 이전 노드에 접근할 수 있습니다.

 

원형 연결 리스트

· 이중 연결 리스트(Doubly Linked List)

단순 연결 리스트에서 이전 노드에 접근하기가 어렵다는 점을 개선하여 원형 연결 리스트를 구성했지만, 원형 연결 리스트에서도 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제가 있습니다. 따라서 이러한 문제를 개선하여 양쪽 방향으로 순회할 수 있도록 연결한 리스트가 이중 연결 리스트입니다.

 

이중 연결 리스트 노드

이중 연결 리스트

연결 리스트 구현

· ListNode

public class ListNode {
	private String data; // 데이터 필드
	public ListNode link; // 링크 필드

	public ListNode(String data) {
		this.data = data;
		this.link = null;
	}

	public String getData() {
		return this.data;
	}
}

 

· SinglyLinkedList

public class SinglyLinkedList {
	private ListNode head;

	// 단순 연결 리스트 초기화
	public SinglyLinkedList() {
		this.head = null;
	}

	// 리스트의 첫 번째 위치에 노드 삽입
	public void insertFirstNode(String data) {
		ListNode newNode = new ListNode(data);

		if (head == null) {
			head = newNode;
		} else {
			newNode.link = head;
			head = newNode;
		}
	}

	// 이전 노드를 입력 받아 중간 위치에 노드 삽입
	public void insertMiddleNode(ListNode preNode, String data) {
		ListNode newNode = new ListNode(data);
		newNode.link = preNode.link;
		preNode.link = newNode;
	}

	// 리스트의 마지막 위치에 노드 삽입
	public void insertLastNode(String data) {
		ListNode newNode = new ListNode(data);
		ListNode temp;

		if (head == null) {
			head = newNode;
		} else {
			temp = head;
			while (temp.link != null) {
				temp = temp.link;
			}
			temp.link = newNode;
		}
	}

	// 리스트의 첫 번째 노드 삭제
	public void deleteFirstNode() {
		if (head == null) {
			return;
		} else {
			head = head.link;
		}
	}

	// 이전 노드를 입력 받아 중간 위치의 노드 삭제
	public void deleteMiddleNode(ListNode preNode) {
		ListNode target = preNode.link;

		if (target == null) {
			return;
		}
		preNode.link = target.link;
	}

	// 리스트의 마지막 노드 삭제
	public void deleteLastNode() {
		ListNode pre, temp;

		if (head == null) { // 빈 리스트일 때
			return;
		}

		if (head.link == null) { // 노드가 한 개일 때
			head = null;
		} else { // 노드가 두 개 이상일 때
			pre = head;
			temp = head.link;
			while (temp.link != null) {
				pre = temp;
				temp = temp.link;
			}
			pre.link = null;
		}
	}

	// 리스트의 노드를 역순으로 변경
	public void reverseList() {
		ListNode next = head;
		ListNode current = null;
		ListNode pre = null;

		while (next != null) {
			pre = current;
			current = next;
			next = next.link;
			current.link = pre;
		}
		head = current;
	}

	// 노드 검색
	public ListNode searchNode(String data) {
		ListNode temp = head;

		while (temp != null) {
			if (temp.getData() == data) {
				return temp; // 검색 성공
			}
			temp = temp.link;
		}
		return temp; // 검색 실패
	}

	// 리스트 출력
	public void printList() {
		ListNode temp;

		if (head == null) {
			System.out.println("빈 리스트입니다.\n");
		} else {
			temp = head;
			System.out.printf("List = [");
			while (temp.link != null) {
				System.out.printf("%s, ", temp.getData());
				temp = temp.link;
			}
			System.out.printf("%s]\n\n", temp.getData());
		}
	}
}

 

· MainForSinglyLinkedList

public class MainForSinglyLinkedList {
	public static void main(String[] args) {
		SinglyLinkedList l = new SinglyLinkedList();
		ListNode node = null;

		System.out.println("1. 리스트에 원소 4개 삽입하기");
		l.insertFirstNode("A");
		l.insertLastNode("B");
		l.insertLastNode("C");
		l.insertLastNode("E");
		l.printList();

		System.out.println("2. C 뒤에 D 삽입하기");
		node = l.searchNode("C");
		if (node == null) {
			System.out.println("해당 원소가 리스트에 없습니다.");
		} else {
			l.insertMiddleNode(node, "D");
			l.printList();
		}

		System.out.println("3. 리스트의 원소를 역순으로 변경하기");
		l.reverseList();
		l.printList();

		System.out.println("4. 리스트 노드 삭제하기");
		l.deleteFirstNode();
		l.deleteLastNode();
		node = l.searchNode("D");
		if (node == null) {
			System.out.println("해당 원소가 리스트에 없습니다.");
		} else {
			l.deleteMiddleNode(node);
			l.printList();
		}
	}
}

 

· 실행 결과

4. 연결 리스트 장점

① 연결 리스트는 원소의 논리적인 순서와 물리적인 순서를 일치시킬 필요가 없습니다. 연속한 메모리 물리주소에 원소의 순서를 표현하는 것이 아니라, 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해 연결되는 방식이기 때문에 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않습니다.

 

② 하나의 고정크기 메모리 공간을 사용하는 순차 자료구조와 달리, 연결 자료구조에서는 여러 개의 작은 공간을 연결하여 전체를 표현하므로 크기 변경이 유연하고 효율적으로 메모리를 사용할 수 있습니다.

5. 연결 리스트 단점

① 원소들이 메모리 물리주소에 연속으로 위치하지 않아 특정 원소의 접근이 오래 걸립니다.

 

② 참조를 위해 추가적인 메모리 공간이 필요합니다.

 

1. 원형 연결 리스트(Circular Linked List)

단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트를 원형 연결 리스트(Circular Linked List)라고 합니다.

 

원형 연결 리스트

단순 연결 리스트는 시작 노드에서 링크를 따라 이동하여 마지막 노드까지 순회할 수 있지만, 현재 노드에서 이전 노드를 접근하려면 항상 리스트의 첫 번째 노드부터 다시 접근해야 합니다.

 

하지만 마지막 노드와 첫 번째 노드가 연결된 원형 연결 리스트에서는 링크를 따라 순회하면 이전 노드에 접근할 수 있습니다.

2. 원형 연결 리스트 구현

원형 연결 리스트는 리스트의 마지막 노드의 링크를 첫 번째 노드로 연결하는 부분만 제외하고 단순 연결 리스트 구현과 동일합니다.

 

· ListNode

public class ListNode {
	private String data; // 데이터 필드
	public ListNode link; // 링크 필드

	public ListNode(String data) {
		this.data = data;
		this.link = null;
	}

	public String getData() {
		return this.data;
	}
}

 

· CircularLinkedList

public class CircularLinkedList {
	private ListNode head;

	// 원형 연결 리스트 초기화
	public CircularLinkedList() {
		this.head = null;
	}

	// 리스트의 첫 번째 위치에 노드 삽입
	public void insertFirstNode(String data) {
		ListNode newNode = new ListNode(data);
		ListNode temp;

		if (head == null) {
			newNode.link = newNode;
			head = newNode;
		} else {
			temp = head;
			while (temp.link != head) {
				temp = temp.link;
			}
			temp.link = newNode;
			newNode.link = head;
			head = newNode;
		}
	}

	// 이전 노드를 입력 받아 중간 위치에 노드 삽입
	public void insertMiddleNode(ListNode preNode, String data) {
		ListNode newNode = new ListNode(data);
		newNode.link = preNode.link;
		preNode.link = newNode;
	}

	// 리스트의 마지막 위치에 노드 삽입
	public void insertLastNode(String data) {
		ListNode newNode = new ListNode(data);
		ListNode temp;

		if (head == null) {
			newNode.link = newNode;
			head = newNode;
		} else {
			temp = head;
			while (temp.link != head) {
				temp = temp.link;
			}
			temp.link = newNode;
			newNode.link = head;
		}
	}

	// 리스트의 첫 번째 노드 삭제
	public void deleteFirstNode() {
		ListNode temp;

		if (head == null) {
			return;
		}
		if (head.link == head) { // 노드가 한 개일 때
			head = null;
		} else { // 노드가 두 개 이상일 때
			temp = head;
			while (temp.link != head) {
				temp = temp.link;
			}
			temp.link = head.link;
			head = temp.link;
		}
	}

	// 이전 노드를 입력 받아 중간 위치의 노드 삭제
	public void deleteMiddleNode(ListNode preNode) {
		ListNode target = preNode.link;
		if (target == head) {
			head = head.link;
		}
		preNode.link = target.link;
	}

	// 리스트의 마지막 노드 삭제
	public void deleteLastNode() {
		ListNode pre, temp;

		if (head == null) { // 빈 리스트일 때
			return;
		}

		if (head.link == head) { // 노드가 한 개일 때
			head = null;
		} else { // 노드가 두 개 이상일 때
			pre = head;
			temp = head.link;
			while (temp.link != head) {
				pre = temp;
				temp = temp.link;
			}
			pre.link = temp.link;
		}
	}

	// 리스트의 노드를 역순으로 변경
	public void reverseList() {
		ListNode next = head;
		ListNode current = null;
		ListNode pre = null;

		do {
			pre = current;
			current = next;
			next = next.link;
			current.link = pre;
		} while (next != head);
		head.link = current;
		head = current;
	}

	// 노드 검색
	public ListNode searchNode(String data) {
		ListNode temp = head;

		do {
			if (temp.getData() == data) {
				return temp; // 검색 성공
			}
			temp = temp.link;
		} while (temp != head);

		return null; // 검색 실패
	}

	// 리스트 순회
	public void traversal(String start, String end) {
		ListNode to = searchNode(start);
		ListNode from = searchNode(end);
		ListNode temp;

		if (to == null || from == null) {
			System.out.println("해당 원소가 리스트에 없습니다.\n");
		} else {
			temp = to;
			while (temp != from) {
				System.out.printf("%s -> ", temp.getData());
				temp = temp.link;
			}
			System.out.printf("%s\n\n", temp.getData());
		}
	}

	// 리스트 출력
	public void printList() {
		ListNode temp;

		if (head == null) {
			System.out.println("빈 리스트입니다.\n");
		} else {
			temp = head;
			System.out.printf("L = [");
			do {
				System.out.printf("%s", temp.getData());
				temp = temp.link;
				if (temp != head) {
					System.out.printf(", ");
				}
			} while (temp != head);
			System.out.printf("]\n\n");
		}
	}
}

 

· MainForCircularLinkedList

public class MainForCircularLinkedList {
	public static void main(String[] args) {
		CircularLinkedList cL = new CircularLinkedList();
		ListNode node;

		System.out.println("1. 리스트에 원소 4개 삽입하기");
		cL.insertFirstNode("A");
		cL.insertLastNode("B");
		cL.insertLastNode("C");
		cL.insertLastNode("E");
		cL.printList();

		System.out.println("2. C 뒤에 D 삽입하기");
		node = cL.searchNode("C");
		if (node == null) {
			System.out.println("해당 원소가 리스트에 없습니다.");
		} else {
			cL.insertMiddleNode(node, "D");
			cL.printList();
		}

		System.out.println("3. D에서 B까지 순회하기");
		cL.traversal("D", "B");

		System.out.println("4. 리스트의 원소를 역순으로 변경하기");
		cL.reverseList();
		cL.printList();

		System.out.println("5. C에서 D까지 순회하기");
		cL.traversal("C", "D");

		System.out.println("6. 리스트 노드 삭제하기");
		cL.deleteFirstNode();
		cL.deleteLastNode();
		node = cL.searchNode("D");
		if (node == null) {
			System.out.println("해당 원소가 리스트에 없습니다.");
		} else {
			cL.deleteMiddleNode(node);
			cL.printList();
		}
	}
}

 

· 실행 결과