자바 LinkedList
목차
링크드 리스트는 컴퓨터 구조에 있어서 상당히 중요한 자료형입니다. 요새 블록체인의 중요성이 커지면서 링크드 리스트와 비교를 많이 합니다. 블록체인은 링크드 리스트와는 다르지만 머리속에 이미지를 그려보면 생긴 그림은 비슷하게 나옵니다. 블록체인에서는 각 노드를 통과하려면 해시가 필요하며 좀더 어려운 것은 분산처리 기술입니다.
링크드 리스트하면 흔히 C가 생각나는데 자바에서도 링크드 리스트를 사용할 수 있습니다. 자바의 링크드 리스트는 직접 구현할 수도 있지만… 컬렉션 프레임워크의 링크드 리스트 클래스를 사용할 수 있습니다. ArrayList 와 비슷하기도 하고 다른 점도 있습니다. 주요한 차이는 메소드가 다르다는데에 있습니다.
컬렉션 프레임워크에서 링크드 리스트를 처음 접했다면 정확한 차이점은 모를 수도 있습니다. 그래서 예제로 간단히 원리를 살펴보고 가겠습니다.
자바 링크드 리스트 예제
아래의 예제는 링크드 리스트의 예제입니다. 전체 소스코드는 아니고 클래스로 데이터 정의하는 것과 삽입과 출력 기능만 기초적으로 구현했습니다.
여기서 눈여겨 볼 것은 Node 라는 클래스입니다. Node 는 말하자면 데이터가 저장된 하나의 블록입니다. 블록안에는 데이터 말고 다른 블록으로 연결하는 참조변수가 들어있습니다. C언어라면 직설적으로 메모리로 향하고 자바에서는 JVM이 사용하는 해시코드가 됩니다.
방식은 다르지만 다음 노드의 주소를 가리키고 있기 때문에 하나의 리스트로써 연결됩니다. 링크드 리스트의 마지막은 null 값을 가져서 리스트의 끝임을 표시합니다.
package com.kay;
public class Main {
public static void main(String[] args) {
LinkedList myList = new LinkedList();
System.out.println("[LinkedList 생성]");
System.out.println("-- myList.head = " + myList.head);
myList.insertNode(111);
myList.insertNode(333);
myList.insertNode(555);
myList.insertNode(777);
myList.insertNode(999);
myList.showLinkedList();
}
}
class LinkedList{
Node head;
// 첫번째 노드(노드 생성시)
LinkedList(){
head = null;
}
// preNode 뒤에 삽입 (중간 삽입)
public void insertNode(Node preNode, int data){
Node newNode = new Node(data);
newNode.next = preNode.next;
preNode.next = newNode;
}
// 마지막 삽입
public void insertNode(int data){
Node newNode = new Node(data);
if (this.head == null){
this.head = newNode;
} else{
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = newNode;
}
}
public void showLinkedList(){
Node temp = this.head;
while(temp != null){
System.out.print(temp.getData() + " : ");
System.out.println(temp.next);
temp = temp.next;
}
System.out.println();
}
}
class Node {
private int data;
Node next;
Node(){
this.data = 0;
this.next = null;
}
Node(int data){
this.data = data;
this.next = null;
}
Node(int data, Node next){
this.data = data;
this.next = next;
}
public int getData(){
return this.data;
}
}[LinkedList 생성] -- myList.head = null 111 : com.kay.Node@7291c18f 333 : com.kay.Node@34a245ab 555 : com.kay.Node@7cc355be 777 : com.kay.Node@6e8cf4c6 999 : null
위의 결과값에서 볼 수 있는 것은 각 객체들의 주소가 다르다는 것 입니다. 각 노드(블록)들은 주소간의 링크로 연결되어 있습니다. 이런 상황에서 인덱스를 사용할 수는 없습니다. 그만큼 속도가 느려지겠지만 중간에 삽입이 어려운 배열과 달리 데이터의 삽입이 빠릅니다. 순수 LinkedList 는 중간에 삽입이 자유롭습니다.
자료형들은 각자 알고리즘에 따라 장단점이 있습니다. 그러나 너무 심각하게 생각할 필요는 없습니다. 24시간 서비스하는 웹의 DB가 아니면 자료 구조를 변환해서 처리하는 방법도 있습니다. 교과서의 내용은 정석적인 내용으로 이해하면 충분합니다.
자바나 C언어의 링크드 리스트의 구현은 인터넷에 찾아보면 잘 나와있습니다. 한가지 팁은 중간에 막히면 그림을 그려가며 자료구조를 만든다면 시각적으로 이해가 빠릅니다.
NODE1 — NODE2 — NODE3 —
head — data/next — data/next —
컬렉션 프레임워크 Linked List
컬렉션 프레임워크로 Linked List 를 구현하는 것은 더 쉽습니다. 사실 직접 구현해보지 않으면 링크드 리스트인지 ArrayList 인지 차이점이 잘 와닿지는 않습니다.
그런 요소들은 다 숨겨져 있습니다. 자바는 응용 프로그래머들이 최대한 모른 상태에서 최대한 결과물을 뽑을 수 있도록 배려하는 철학에서 출발했습니다. Write Once Run Anywhere (한번 쓰고 어디서든 실행해라)라는 모토를 걸고 나왔기 때문이죠.
실제로 한번 쓰고 어디서든 실행은 가능하긴 한데 당연히 좀 손은 봐줘야 합니다. 그런 것보다 요새는 클라우드 기술이 더 마음적으로 끌리게 됩니다. 여하튼 프로그래머건 일반인이건 일을 줄여주는 코드는 계속 진화하고 있습니다. 그럼에도 이렇게 Base 가 되는 기술을 배우는 이유는 간단합니다. 그 다음 단계로 나아가기 위해서입니다.
아래의 코드를 보면 java.util 패키지에서 LinkedList 클래스를 가져옵니다.
이전 학습에서 사용한 사용자 정의 데이터형인 MyMemo 를 사용합니다. 이것을 사용하는 이유는 가장 만만한 클래스이기 때문입니다. (간단한 데이터형을 무시하면 안됩니다. 간단한 것이 가장 파워풀하니까요)
이렇게 보면 ArrayList 와 차이점이 별로 없습니다. 메소드가 몇개 다르게 보입니다. 중요한 차이점은 내부에 있는데 여기선 보이지 않습니다. 가장 잘 이해가 가려면 역시 C나 C++ 알고리즘의 학습을 추천합니다.
package com.kay;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<MyMemo> myList = new LinkedList<MyMemo>();
myList.add(new MyMemo(2001, "Chapter 2"));
myList.add(new MyMemo(2002, "Linked List Found"));
myList.add(new MyMemo(2003, "Linked List seems like Blockchain"));
myList.add(new MyMemo(2004, "But it's not"));
for (MyMemo memo : myList){
System.out.println("id = " + memo.getMemoId() + ", text = " + memo.getMemoText());
}
System.out.println("-----------------------------");
myList.add(2, new MyMemo(7777, "Interrupt"));
myList.addFirst(new MyMemo(9999, "Zero"));
myList.removeLast();
for (MyMemo memo : myList){
System.out.println("id = " + memo.getMemoId() + ", text = " + memo.getMemoText());
}
}
}
class MyMemo{
private int memoId;
private String memoText;
public int getMemoId() {
return memoId;
}
public void setMemoId(int memoId) {
this.memoId = memoId;
}
public String getMemoText() {
return memoText;
}
public void setMemoText(String memoText) {
this.memoText = memoText;
}
public MyMemo(int memoId, String memoText) {
this.memoId = memoId;
this.memoText = memoText;
}
}
id = 2001, text = Chapter 2 id = 2002, text = Linked List Found id = 2003, text = Linked List seems like Blockchain id = 2004, text = But it's not ----------------------------- id = 9999, text = Zero id = 2001, text = Chapter 2 id = 2002, text = Linked List Found id = 7777, text = Interrupt id = 2003, text = Linked List seems like Blockchain
사용자체는 어렵지 않아서 메소드만 몇개 실행해봐도 충분할 겁니다.
요약
자바 LinkedList 에 대해서 대강 알아봤습니다. 자바도 알고리즘 교재들이 있으니까 중급단계로 가기전에 한번쯤 익혀두는 것을 추천합니다.
여기서는 콜렉션 프레임워크의 링크드 리스트를 소개하려는 의도였으나 별로 ArrayList 와 차이가 잘 안보일 겁니다. 원래 사용하는 사람은 차이를 잘 모르는 겁니다. 구현하는 사람에게 쎄빠지는 일이 와닿지가 않죠.
기초적인 부분이라도 직접 구현해보는 것을 추천하겠습니다.
외부참고문서
자바 LinkedList (Java Platform SE 7 ) (oracle.com)
Implementing a Linked List in Java using Class – GeeksforGeeks
Blockchain vs Linked List: Is Blockchain a Linked List? | 101 Blockchains