리스트
- 순서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type)
- 동일한 데이터를 가지고 있어도 상관 없음
구현 방법에 따른 분류
1) 순차 리스트 : 배열을 기반으로 구현된 리스트
2) 연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트
연결 리스트
- 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로
위치하고 있는 각 원소를 연결하여 하나의 전체적인 자료구조를 이룬다.
- 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한
작업이 필요하지 않다
- 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.
연결 리스트의 기본 구조
1. 노드
- 연결 리스트에서 하나의 원소를 표현하는 building block
- 구성 요소
1) 데이터 필드
- 원소의 값을 저장
- 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용
2) 링크 필드
- 다음 노드의 참조값을 저장
2. 헤드
- 연결 리스트의 첫 노드에 대한 참조값을 가짐
연결 리스트 - 단순 연결 리스트 (Singly Linked List)
- 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.
- 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
- 링크 필드가 Null인 노드가 연결 리스트의 가장 마지막 노드이다.
단순 연결 리스트의 삽입 연산 - 첫번째 노드로 삽입
- 내가 첫째가 되려면 첫째를 내 뒤에 세우면 된다!!
단순 연결 리스트의 삽입 연산 - 마지막 노드로 삽입
코드로 구현 시 위에서 설명한 첫번째 노드로 삽입 코드의 재사용으로 최초 노드 추가를
단순화 할 수 있다.
또한 마지막 노드 구하기 코드 역시 미리 구현해놓아서 재사용이 가능하다.
단순 연결 리스트의 삽입 연산 - 중간 노드로 삽입
나의 링크 ← 이전 노드의 링크
이전 노드의 링크 → 나
단순 연결 리스트의 삽입 연산 - 삭제 연산
이전 노드의 링크 ← 나의 링크
나 삭제
단순 연결 리스트 Java 구현
public class SinglyLinkedList {
private Node head; // 첫번째 노드를 저장 (별도의 head가 첫번째 Node를 가리키는 형태 아님!)
//첫번째 노드로 삽입하기
public void addFirstNode(String data) {
// 내가 첫째가 되려면 첫째를 내 뒤에 세우면 된다.
Node newNode = new Node(data, head);
head = newNode;
}
// 마지막 노드 찾기
public Node getLastNode() {
for(Node currNode = head; currNode != null; currNode = currNode.link) {
// 자신의 뒤에 아무도 없으면 자신이 막내
if(currNode.link == null) return currNode;
}
return null;
}
// 마지막 노드로 삽입하기
public void addLastNode(String data) {
if(head == null) {// 공백리스트
addFirstNode(data);
return;
}
Node lastNode = getLastNode();
lastNode.link = new Node(data, null);
}
// 선행 노드를 기준으로, 그 노드 뒤에 data를 가지는 노드 삽입
public void insertAfterNode(Node preNode, String data) {
if(preNode == null) {
System.out.println("선행노드가 없어 삽입이 불가능합니다.");
return;
}
// 나의 링크를 이전 노드의 링크(다음노드)로
// 선행노드의 링크를 지금 만드는 Node로 바꾼다.
Node newNode = new Node(data, preNode.link);
preNode.link = newNode;
}
// data를 데이터로 갖고 있는 처음 만나는 노드 리턴
public Node getNode(String data) {
for(Node currNode = head; currNode != null; currNode = currNode.link) {
if(currNode.data.equals(data)) {
return currNode;
}
}
return null;
}
// target의 이전노드 찾기
// 특정 Node의 링크값이 나를 가리키고 있으면 -> 그것이 이전 노드
public Node getPreviousNode(Node target) {
for(Node currNode = head; currNode != null; currNode = currNode.link) {
if(currNode.link == target) {
return currNode;
}
}
return null;
}
// data를 가지고 있는 첫번째 노드 찾아서 삭제
public void deleteNode(String data) {
Node targetNode = getNode(data);
if(targetNode == null) {
System.out.println("삭제할 노드가 없어서 삭제가 불가능합니다.");
return;
}
Node preNode = getPreviousNode(targetNode);
if(preNode == null) { // 이전 노드가 없다 -> target이 head인 상황
head = targetNode.link;
}else { // target이 첫번째 노드가 아닌 상황
preNode.link = targetNode.link;
}
targetNode.link = null;
}
public void printList() {
System.out.print("L = ( ");
for(Node currNode = head; currNode != null; currNode = currNode.link) {
System.out.print(currNode.data + " ");
}
System.out.println(" ) ");
}
}
Java
복사
이중 연결 리스트
- 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
- 두개의 링크 필드와 한 개의 데이터 필드로 구성
이중 필드로 구성되어 있기에 단일 연결 리스트보다 삽입, 삭제 연산 시 추가 동작 구현이 필요하다.
ex) 이전 노드 - 삽입 - 다음 노드
1. 나의 next ← 이전 노드의 next
2. 나의 prev ← 다음 노드의 prev
3. 이전 노드의 next ← 나
4. 다음 노드의 prev ← 나
