안녕하세요!
오늘 공부한 Linked List 에 대해서 간단하게 적어보겠습니다.
리스트
자바에서 리스트는 원소를 관리하는 순서를 가진 데이터의 집합을 가리키는 추상적인 자료형입니다.
동일한 데이터를 가지고 있어도 상관 없습니다.
리스트는 구현 방법에 따라 순차 리스트 와 연결 리스트로 나뉩니다.
- 순차 리스트 : 배열 기반의 리스트
- 연결 리스트 : 메모리 동적 할당을 기반으로 구현하는 리스트
순차 리스트
순차 리스트는 쉽게 말해서 자바의 배열을 뜻합니다.
순차 리스트에서는 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있습니다.
순차 리스트에서 삽입 연산은 아래의 순서대로 실행됩니다.
1. 삽입할 인덱스를 비워둬야 합니다.
2. 삽입할 인덱스가 배열의 마지막이 아닌 가장 앞 또는 중간이라면 삽입 위치 다음의 항목들을 모두 뒤로 이동시켜야 합니다.
3. 그 후 삽입 위치에 원하는 데이터를 삽입합니다.
삭제 연산은 위의 삽입 연산의 플로우에서, 다음 항목들을 앞으로 이동시키는 것 외에 다른 점은 없습니다.
단순 배열로 순차 리스트를 구현할 때의 문제점
- 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시켜야 한다.
- 원소의 개수가 많을 경우 삽입/삭제 연산에 소요되는 시간이 크게 증가한다.
- 배열의 크기를 실제 원소의 개수보다 크게 할당할 경우에는 메모리 낭비를, 실제 원소 개수보다 작게 할당할 경우에는 새로운 배열을 만들어 작업해야 하는 문제점이 있다.
연결 리스트
연결 리스트는 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 각 원소들을 연결해 하나의 자료구조를 이룹니다.
링크를 통해 원소에 접근하므로, 순차 리스트처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않습니다.
또한 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능합니다.
연결 리스트에는 링크를 하나만 유지하는 단순 연결 리스트, 링크를 2개 유지하는 이중 연결 리스트, 링크의 끝을 처음에 연결하는 원형 연결 리스트가 있습니다.
노드
노드는 연결 리스트에서 하나의 원소를 뜻하는 빌딩 블록입니다.
노드에는 원소의 값을 저장하는 데이터 필드 와 다음 노드의 참조값을 저장하는 링크 필드 가 있습니다.
또한 헤드 노드 에는 연결 리스트의 첫 노드에 대한 참조값을 갖고 있습니다.
이중 연결 리스트는 연결 리스트의 마지막 노드의 참조값을 갖는 테일 을 추가해서 구현한 것을 의미합니다.
자바로 단순 연결 리스트 구현하기
public class Node {
// 데이터 필드
public String data;
// 링크 필드
public Node link;
public Node(String data) {
super();
this.data = data;
}
public Node(String data, Node link) {
this(data);
this.link = link;
}
}
Node 클래스입니다.
데이터 필드와 링크 필드를 구현하는데, 여기서 링크 필드는 다음 노드의 참조값을 의미하므로 참조 타입은 Node 입니다.
그 후에 데이터만으로 노드를 생성하는 방법과 링크의 참조값까지 포함해서 노드를 생성하는 방법 두 가지를 구현하기 위해 생성자를 오버로딩해서 두 개 만들었습니다.
public class SinglyLinkedList {
private Node head; // 첫번째 노드 저장
// 첫번째 노드로 삽입하기
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 newNode = new Node(data);
Node lastNode = getLastNode();
lastNode.link = newNode;
}
// ...
}단순 연결 리스트인 SinglyLinkedList 입니다.
멤버 변수로는 head 만 가집니다.
만약, 이중 연결 리스트라면 tail 도 포함해야겠죠?
첫번째 노드를 삽입하는 것은, head가 해당 노드라는 것이므로 위와 같이 처리합니다.
단순 연결 리스트이기 때문에 마지막 노드를 찾아오는 것은 리스트를 모두 순회한 후에 링크 필드가 null 인,즉 다음 값이 없는 노드를 반환합니다.
연장선으로 마지막 노드로 삽입하는 것은 새로운 노드를 현재 마지막 노드의 링크 필드에 연결시켜주는 것입니다.
public class SinglyLinkedList {
// ...
// 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의 이전노드 찾기
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;
}
}Node 의 data 를 검색하는 기능은 마찬가지로 리스트를 순회하면서, data 가 매개변수로 받은 data 와 동일한지 체크 후에, 동일하면 해당 노드를 반환합니다.
그럼 target 의 이전 노드는 어떻게 찾을까요?
link 필드가 target 인 노드를 찾으면 됩니다.
즉, 이전 노드를 찾는 것이 되겠습니다.
삭제 기능은 삭제할 노드를 link 하고 있는 노드를 찾아서 삭제할 노드가 link 중인 참조값을 넣어줍니다.
그 후 삭제할 노드의 link 필드를 null로 초기화해야 합니다.
이는 링크 연결을 끊는 것과 동일합니다.
직접 자료구조를 구현해보니, 더 잘 이해가 됐던 것 같습니다.
실제로 알고리즘 시험에서 직접 필요한 기능만 구현하는 방법이 시간적으로 더 효율적일 때도 있다고 합니다~!
오늘도 포스팅 읽어주셔서 감사합니다 :)
