[자료구조] Linked List란? - Java 구현
순서
ㄴ Single Linked List와 Doubly Linked List 차이점(Doubly Linked List가 필요한 이유)
🤔 Linked list 란 무엇인가?
List와의 차이점
연결된 리스트란 의미를 가지는 링크드 리스트는 일반 리스트(List)와 차이점을 보면서 이야기할 수 있다.
기본적인 List는 순차적으로 데이터가 저장된 배열 구조이다.
List 구조
| index(순서) | 0 | 1 | 2 | 3 | 4 | 5 |
| value(값) | "첫번째 값" | "두번째 값" | "세번째 값" | "네번째 값" | "다섯번째 값" | "여섯번째 값" |
위 표와 같은 List가 저장되어있다면 해당 리스트는 ["첫번째 값", "두번째 값", "세번째 값", "네번째 값" ...] 와 같이 순차적으로 값을 갖는 것이다. (순서대로 비어있는 공간에 저장)
하지만, 일반적인 List의 경우 선언할 당시에 배열의 크기를 정해줘야한다.
ex) String[] list = String[6]; => 크기가 6인 문자열 배열
그렇기에 메모리는 낭비하지 않기 위해서 필요한 크기만큼만 정의해서 사용하는게 효율적인데 만일, 가변적으로 크기가 변해야하는 상황이라면, 이 처럼 List를 사용하는게 쉽지 않다.
Linked List는 배열의 크기를 미리 정해주지 않고 필요할 때 마다 노드(node)를 추가하고 연결해 줌으로서 가변적인 상황에 대처할 수 있다.
여기서 노드란, 하나의 값(value)를 갖고 있는 공간을 의미한다. 위의 List 테이블에서 한 칸에 하나의 value를 갖는데 이 공간은 노드라고 보면 된다.
Linked List의 모습을 보면 아래와 같다.
Single Linked List
node 안에는 데이터 값인 value와 다른 node의 위치 정보(컴퓨터 메모리 주소)를 가진다.
하나의 node를 알면 다른 node들을 모두 찾아갈 수 있다. 추가적인 data를 저장할 필요가 있을 때 node를 생성하고 맨 끝 pointer에 새로운 Node의 위치를 저장하면 연결된 구조를 만들 수 있다.
이렇게 하나의 노드가 데이터 값과 다른 노드의 위치 정보를 가지고 있으면 Linked List라고 할 수 있다.
위 그림과 같이 하나의 pointer(다음 순서의 node 위치 정보)를 가지면 Single Linked List라고 한다.
위 그림과 같이 pointer가 2개 존재해 이전 node의 위치 정보와 다음 node의 위치 정보를 모두 가지고 있는 node들이 서로 연결되어 있다면 Doubly Linked List라고 한다.
그럼 Doubly Linked List는 왜 필요할까?
Single Linked List의 경우 pointer가 자신의 다음 node만을 가르키기 때문에 모든 값을 조회, 삽입, 삭제하기 위해서는 기준이 될 수 있는 제일 앞의 node (여기선 head)를 알아야 한다.
특정 node를 찾기 위해서는 head를 시작으로 찾을 data와 일치하는지 확인하고 아닐 경우 head의 pointer에서 다음 node의 위치를 확인하고 이동해 다시 data가 일치하는지 확인하는 것을 반복해야 한다.
만약에 찾아야할 값이 node의 끝부분에 있었다면 상당히 비효율적이게 된다. 찾아야할 데이터가 앞에있을지 뒤에 있을지 예측할 수 있다면, 양쪽에서 모두 시작할 수 있는 것이 효율적일 것이다.
이때 사용가능한 것이 doubly Linked List이다.
Doubly Linked List의 경우, pointer로 앞의 node와 뒤의 node를 모두 확인할 수 있어서 상황에 맞게 뒤에서 탐색을할 것인지 맨 앞에서 탐색을할 것인지 결정할 수 있다.
😃 Single Linked List 구현하기 for Java
public class SingleLinkedList<T> {
// 기준이 되는 가장 첫번째 node
public Node<T> head = null;
// 내장 객체 Node 정의
public class Node<T> {
T data;
Node<T> next = null;
// Node class의 생성자
public Node(T data) {
this.data = data;
}
}
// 맨 끝 단에 노드 추가
public void addNode(T newData) {
if(head == null) { // List는 비어있는 상태
head = new Node<>(newData);
}
else { // 비어있지 않다면 가장 끝 node를 탐색
// head 로 이동
Node<T> node = this.head;
// node의 next가 null 일 때 까지
while (node.next != null) {
node = node.next;
}
// 다음 링크를 연결
node.next = new Node<T>(newData);
}
}
// 노드 중간 추가
public void insertNode(T data, T where){ // data: 삽입할 데이터, where: 삽입할 데이터의 기준 위치
Node<T> searchNode = this.search(where);
if (searchNode == null) {
this.addNode(data);
} else {
Node<T> nextNode = searchNode.next;
searchNode.next = new Node<>(data); // 기준점 뒤에 삽입
searchNode.next.next = nextNode; // 새로 삽입한 데이터에 기준점의 기존 next를 삽입
}
}
// node 검색
public Node<T> search(T where) {
if (this.head == null) {
return null;
} else {
Node<T> node = head;
while(node.next != null) {
if(node.data == where){
return node;
} else {
node = node.next;
}
}
// 모든 탐색 후 없다면 null 리턴
return null;
}
}
// node 삭제 메소드
public boolean delNode(T data) {
if(this.head == null) {
return false;
} else {
Node<T> node = this.head;
if(node.data == data) {
this.head = this.head.next;
return true;
} else {
// node 이동
while(node.next != null) {
if(node.next.data == data) {
node.next = node.next.next;
return true;
} else {
node = node.next;
}
// 모든 탐색을 마친 후 없으면 false;
}
return false;
}
}
}
}
😃 Doubly Linked List 구현하기 for Java
public class DoublyLinkedList<T> {
public Node<T> head; // 가장 앞의 node
public Node<T> tail; // 가장 뒤의 node
// 내장 객체 node
public class Node<T>{
T data;
Node<T> prev; // 앞 node의 pointer
Node<T> next; // 뒤 node의 pointer
public Node(T data) { // 생성자
this.data = data;
}
}
// 맨 끝에 node 추가하기
public void addNode(T data) {
if(this.head == null){
this.head = new Node<>(data);
this.tail = this.head;
} else {
Node<T> node = head;
while(node.next != null){
node = node.next;
}
node.next = new Node<>(data);
node.next.prev = node;
this.tail = node.next;
}
}
// head에서 특정 값 찾기
public T findFromHead(T data) {
if(this.head != null) {
Node<T> node = head;
while(node != null) {
if(node.data == data) {
return node.data;
} else {
node = node.next;
}
}
return null;
}
return null;
}
// 맨 뒤 node에서 특정 값 찾기
public T findFromTail(T data) {
if(this.tail != null) {
Node<T> node = this.tail;
while(node != null) {
if(node.data == data){
return node.data;
} else {
node = node.prev;
}
}
return null;
}
return null;
}
// param의 값을 가지는 Node에 node 추가하기(head 에서부터 찾기)
public boolean addNodeToFront(T addData, T targetData){
if(this.head == null) {
this.head = new Node<>(addData);
this.tail = this.head;
return true;
} else if(this.head.data == targetData) {
Node<T> newHead = new Node<>(addData);
newHead.next = this.head;
this.head = newHead;
this.head.next.prev = this.head;
return true;
} else {
Node<T> node = this.head;
while (node != null) {
if(node.data == targetData){
Node<T> addNode = new Node<>(addData);
addNode.prev = node.prev;
addNode.next = node;
node.prev.next = addNode;
node.prev = addNode;
return true;
} else{
node = node.next;
}
}
return false;
}
}
}