링크드 리스트 (Linked List), 대학교의 자료 구조 수업을 듣기 시작하면 무조건, 반드시, 꼭 한번 들어보는 녀석입니다. 그리고 반드시 구현 과제를 내곤 하죠! 대체 뭔데 이렇게 중요하게 다룰까요? 대체 뭐하는 녀석인지, 어떻게 만드는지 한 번 알아봅시다.
링크드 리스트 (연결 리스트, Linked List) 란?
"연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다."
위에서 얘기한 것을 보면 연결 리스트엔 2가지 타입이 존재합니다.
- 단일 연결 리스트 : 한 방향으로만 연결된 리스트
- 이중 연결 리스트 : 양 방향으로 연결된 리스트
이 포스팅에서는 단일 연결 리스트가 어떻게 생긴 것인지, 또 어떻게 구현하는 것인지 학습해 볼 예정입니다. 물론 이중 연결 리스트는 다른 포스팅에서 소개할 것입니다.
단일 연결 리스트 구조
일단 단일이든, 이중이든, 연결 리스트를 이루는 가장 작은 단위를 노드 (Node)라고 합니다. 그냥 쉽게 말해서 데이터를 넣는 그릇을 노드라고 부르는 것입니다. 사실 다른 자료 구조에서도 데이터를 담는 그릇을 노드라고 부르는데, 일단은 연결 리스트 구성 요소 = 노드 입니다.
노드에는 개발자가 원하는 여러가지 데이터를 담을 수 있는데, 뭐 숫자를 넣어도 좋고, 문장(String)을 넣어도 좋습니다. 필요한 것을 넣으세요! 이렇게 노드를 줄줄이 소세지처럼 엮은 것이 연결 리스트입니다. 아래의 그림과 같이 말이죠.
그런데 이렇게 만들고보니, 우리는 가장 처음 노드를 어떤 노드로 할 것인지 정하지 않았습니다. 노드를 만들어서 연결을 해야하는데, 어떤 노드부터 시작해야 되는지 모르는 것이죠. 그냥 아무 노드 하나 만들어서 거기서부터 쭉쭉 연결하면 안 되냐구요? 맞습니다. 우리는 그 아무 노드를 헤더 (header) 라는 조금 다른 이름으로 부르기 시작하죠.
이렇게 만들면 맨 처음 연결 리스트를 구현할 때 가장 우선적으로 헤더 노드를 만들어놓고 원하는 형태의 노드를 뒤에 붙이는 식으로 구현하기만 하면 끝입니다.
연결 리스트 구현하기
개념은 무척 간단해서 후딱 지나간 느낌이 없잖아 있는데, 코딩의 어려움은 머릿속에 있는 내용을 코드로 표현하는 것이죠. 어떻게 만들어야 할까요? 아래의 순서를 따라와 보세요.1. Node 클래스 생성
static class Node {
String data; // 데이터는 원하는 것을 넣어주시면 됩니다.
Node next;
public Node(String data) { this.data = data; }
}
일단 기본적인 틀은 갖춰야겠죠. 데이터를 담을 data 변수, 다음 노드를 가리킬 next를 세팅해 줍시다.
2. Header 노드 생성
Node header = new Node("header");
이 Header 노드는 LinkedList 클래스 내에서 생성할 것입니다.
3. LinkedList 클래스 생성
class SinglyLinkedList {
Node header = new Node("header");
int size; // 연결 리스트에 들어있는 노드의 개수를 따로 저장합니다. (순회하기 편하려고)
}
size는 사실 굳이 필요 없긴 한데, 있으면 연결 리스트 크기를 바로 체크할 수 있어서 여러 기능을 구현할 때 편할 수 있습니다.
자, 일단 기본 구조는 설계해놨고, 아래부터는 필요한 함수를 가져다 쓰면 됩니다. 사실 단일 연결 리스트는 삽입 및 삭제가 거의 맨 앞에서 일어나며, 중간 삽입에 능한 자료 구조는 아닙니다. (삽입을 하려면 리스트를 순회를 해야되기 때문에) 그래서 중간 삽입 함수나 삭제는 사실 별로 필요 없긴 한데, 뭐 다양한 형태로 구현해보면 재밌잖아요? 그 외에도 여러 언어에서 기본적으로 제공해주는 함수들을 직접 생각해보고 구현해 봅시다. 아래는 참고로만 봐주시면 될 것 같습니다. (사실 대충 구현해서 제대로 동작하는 지도 잘 모르겠습니다 ㅎㅎㅎ...)
4. addFirst - 헤더 바로 다음에 노드 삽입하기
// 맨 앞에 노드 붙이기 (즉, 헤더 바로 다음에 붙이기)
public static void addFirst(Node node) {
node.next = header.next;
header.next = node;
size++;
}
5. addLast - 연결 리스트의 맨 끝에 노드 삽입하기
public static void addLast(Node node) {
Node curr = header;
while (curr.next != null) {
curr = curr.next;
}
curr.next = node;
size++;
}
6. add - 원하는 위치에 노드 삽입하기
// idx번째 노드 앞에 붙이기
public static void add(Node node, int idx) {
if (idx > size) return;
if (idx == 0) { addFirst(node); return; }
// 헤더부터 시작해서 idx번째 노드 찾기
int cnt = -1;
Node curr = header;
while (curr.next != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
node.next = curr.next;
curr.next = node;
size++;
}
7. removeFirst - 헤더 바로 다음 노드 삭제하기
public static void removeFirst() {
header.next = header.next.next;
size--;
}
8. removeLast - 연결 리스트의 맨 끝 노드 삭제하기
public static void removeLast() {
Node curr = header;
if (curr.next == null) return;
while (curr.next.next != null) {
curr = curr.next;
}
curr.next = null;
size--;
}
9. remove - 원하는 위치의 노드 삭제하기
public static void remove(int idx) {
if (idx > size) return;
if (idx == 0) { removeFirst(); return; }
int cnt = -1;
// 헤더부터 시작해서 idx번째 노드 찾기
Node curr = header;
while (curr != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
curr.next = curr.next.next;
size--;
}
마치며..
뭔가 다른 블로그처럼 자세하게 설명하지 못했네요. 글 쓰다가 뭔가 피곤해 졌어요. 나중에 기회봐서 추가할 내용이나 수정할 내용이 있으면 고쳐 놓도록 하겠습니다. 혹시 이상한 부분이 있으면 "앗, 이거 틀렸다!" 하고 혼내주세요 ㅎㅎ. 굳이 전체 코드가 필요할 것 같진 않지만, 그래도 혹시 모르니 올려 놓겠습니다. 그럼 모두 즐거운 하루 되세요!
class Node {
String data; // 데이터는 원하는 것을 넣어주시면 됩니다.
Node next;
public Node(String data) { this.data = data; }
}
class SinglyLinkedList {
Node header = new Node("header");
int size; // 연결 리스트에 들어있는 노드의 개수를 따로 저장합니다. (순회하기 편하려고)
// 맨 앞에 노드 붙이기 (즉, 헤더 바로 다음에 붙이기)
public void addFirst(Node node) {
node.next = header.next;
header.next = node;
size++;
}
// idx번째 노드 앞에 붙이기
public void add(Node node, int idx) {
if (idx > size) return;
if (idx == 0) { addFirst(node); return; }
// 헤더부터 시작해서 idx번째 노드 찾기
int cnt = -1;
Node curr = header;
while (curr.next != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
node.next = curr.next;
curr.next = node;
size++;
}
public void addLast(Node node) {
Node curr = header;
while (curr.next != null) {
curr = curr.next;
}
curr.next = node;
size++;
}
public void removeFirst() {
header.next = header.next.next;
size--;
}
public void remove(int idx) {
if (idx > size) return;
if (idx == 0) { removeFirst(); return; }
int cnt = -1;
// 헤더부터 시작해서 idx번째 노드 찾기
Node curr = header;
while (curr != null) {
// 다음 노드 탐색
curr = curr.next;
// 찾고자 하는 위치에 도달하면 탐색 종료
if (++cnt == idx - 1) break;
}
curr.next = curr.next.next;
size--;
}
public void removeLast() {
Node curr = header;
if (curr.next == null) return;
while (curr.next.next != null) {
curr = curr.next;
}
curr.next = null;
size--;
}
public void print() {
Node curr = header;
while (curr != null) {
System.out.printf(curr.data + " ");
curr = curr.next;
}
System.out.println("");
}
public static void main(String[] args) {
SinglyLinkedList linkedList = new SinglyLinkedList();
linkedList.print();
linkedList.addFirst(new Node("1"));
linkedList.print();
linkedList.addFirst(new Node("2"));
linkedList.print();
linkedList.addFirst(new Node("3"));
linkedList.print();
linkedList.addFirst(new Node("4"));
linkedList.print();
linkedList.addFirst(new Node("5"));
linkedList.print();
linkedList.add(new Node("6"), 2);
linkedList.print();
linkedList.add(new Node("7"), 0);
linkedList.print();
linkedList.add(new Node("10"), 6);
linkedList.print();
linkedList.add(new Node("71"), 8);
linkedList.print();
linkedList.add(new Node("22"), 1);
linkedList.print();
linkedList.removeFirst();
linkedList.print();
linkedList.removeLast();
linkedList.print();
linkedList.remove(0);
linkedList.print();
linkedList.remove(3);
linkedList.print();
linkedList.remove(5);
linkedList.print();
linkedList.remove(2);
linkedList.print();
}
}
댓글
댓글 쓰기