링크드 리스트
연결 리스트 (Linked List)
연결 리스트의 개념
- 연결 리스트 (Linked List) : 데이터와 포인터를 가진 각 노드들을 일렬로 연결시킨 형태의 자료구조
- 예 : 버킷 리스트, 요일들 등
연결 리스트의 특징
- 메인 메모리상 물리적으로 흩어져있는 데이터들을 서로 연결하여 하나로 묶는 방식
- 삽입/삭제 시 앞뒤에 있는 데이터들을 이동할 필요없이 해당 데이터들을 연결하는 줄만 수정하면 된다.
- 첫 번째 데이터만 알면 나머지 데이터들을 연결된 줄로 추적 가능하다.
- 포인터를 저장하기 위한 추가적인 메모리 공간이 필요하다.
연결 리스트의 구조
- 노드 (node) : 연결되는 상자, 데이터 필드와 링크 필드로 구성
- 데이터 필드 (data field) : 저장하고 싶은 데이터가 들어감
- 링크 필드 (link field) : 다른 노드를 가리키는 포인터가 들어감
- 머리 (head) : 첫 번째 노드
- 꼬리 (tail) : 마지막 노드
연결 리스트의 종류
- 단순 연결 리스트 (singly linked list) :
- 하나의 방향으로만 연결되어 있는 연결 리스트
- 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있음
- 체인(Chain)이라고도 함
- 마지막 노드의 링크 필드는 NULL 값을 가짐
- 원형 연결 리스트 (circular linked list) :
- 단순 연결 리스트와 같으나 마지막 노드가 첫 번째 노드를 가리킴
- 마지막 노드의 링크 필드는 첫 번째 노드 주소를 가리킴
- 하나의 노드에서 다른 모든 노드로 접근이 가능
- 원소가 하나밖에 없으면 자기자신을 가리킴
- 이중 연결 리스트 (doubly linked list) :
- 각 노드마다 2개의 링크가 존재
- 하나의 링크는 앞의 노드를 가리키고 다른 하나의 노드는 뒤의 노드를 가리킴
- 단순 연결 리스트의 단점을 보완하여 특정 노드에서 자유롭게 양방향으로 움직일 수 있음
연결 리스트의 구현
public class SinglyLinkedList {
Node head;
Node tail;
int size;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
size = 0;
}
class Node {
Object data;
Node nextNode;
Node(Object data){
this.data = data;
this.nextNode = null;
}
}
// 특정 노드 위치 검색
public Node search(int idx) {
Node findNode = head; // 머리부터 시작함
for(int i = 0; i < idx; i++) {
findNode = findNode.nextNode;
}
return findNode;
}
// 맨 앞에 추가
public void addFirst(Object data) {
Node newNode = new Node(data);
newNode.nextNode = head;
head = newNode;
size++;
if (head.nextNode == null) {
tail = head;
}
}
// 맨 뒤에 추가
public void addLast(Object data) {
Node newNode = new Node(data);
if (size == 0) {
addFirst(data);
return;
}
tail.nextNode = newNode;
tail = newNode;
size++;
}
// 중간에 추가
public void add(Object data, int idx) {
if (idx == 0) {
addFirst(data);
return;
}
if (idx == size) {
addLast(data);
return;
}
Node preNode = search(idx - 1);
Node postNode = preNode.nextNode;
Node newNode = new Node(data);
preNode.nextNode = newNode;
newNode.nextNode = postNode;
size++;
}
// 맨 앞에 삭제
public Object removeFirst() {
Node headNode = head;
head = head.nextNode;
if (head == null) {
tail = null;
}
size--;
return headNode.data;
}
// 맨 뒤에 삭제
public Object removeLast() {
if (size <= 1) {
return removeFirst();
}
Node secondNode = search(size - 2);
Node lastNode = tail;
tail = secondNode;
tail.nextNode = null;
size--;
return lastNode.data;
}
// 중간에 삭제
public Object remove(int idx) {
if (idx == 0) {
return removeFirst();
}
if (idx == size - 1) {
return removeLast();
}
Node preNode = search(idx - 1);
Node lastNode = preNode.nextNode;
preNode.nextNode = preNode.nextNode.nextNode;
size--;
return lastNode.data;
}
// string으로 데이터 출럭
public String toString() {
StringBuffer str = new StringBuffer("[");
Node node = head;
if (node != null) {
str.append(node.data);
node = node.nextNode;
while(node != null) {
str.append(", ");
str.append(node.data);
node = node.nextNode;
}
}
str.append("]");
return str.toString();
}
public static void main(String[] args) {
SinglyLinkedList linkedList = new SinglyLinkedList();
// 맨 앞에 추가
linkedList.addFirst(1);
linkedList.addFirst(2);
linkedList.addFirst(3);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 1]
// 맨 뒤에 추가
linkedList.addLast(4);
linkedList.addLast(5);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 1, 4, 5]
// 중간에 추가
linkedList.add(10, 2);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 10, 1, 4, 5]
// 맨 앞에 삭제
linkedList.removeFirst();
System.out.println(linkedList.toString()); // 출력 : [2, 10, 1, 4, 5]
// 맨 뒤에 삭제
linkedList.removeLast();
System.out.println(linkedList.toString()); // 출력 : [2, 10, 1, 4]
// 중간에 삭제
linkedList.remove(2);
System.out.println(linkedList.toString()); // 출력 : [2, 10, 4]
}
}
public class CircularLinkedList {
Node head;
Node tail;
int size;
public CircularLinkedList() {
this.head = null;
this.tail = null;
size = 0;
}
class Node {
Object data;
Node nextNode;
Node(Object data){
this.data = data;
this.nextNode = null;
}
}
// 특정 노드 위치 검색
public Node search(int idx) {
Node findNode = head; // 머리부터 시작함
for(int i = 0; i < idx; i++) {
findNode = findNode.nextNode;
}
return findNode;
}
// 맨 앞에 추가
public void addFirst(Object data) {
Node newNode = new Node(data);
if (size == 0) {
head = newNode;
tail = newNode;
newNode.nextNode = head;
}
else {
newNode.nextNode = head;
head = newNode;
tail.nextNode = head;
}
size++;
}
// 맨 뒤에 추가
public void addLast(Object data) {
Node newNode = new Node(data);
if (size == 0) {
addFirst(data);
return;
}
tail.nextNode = newNode;
tail = newNode;
tail.nextNode = head;
size++;
}
// 중간에 추가
public void add(Object data, int idx) {
if (idx == 0) {
addFirst(data);
return;
}
if (idx == size) {
addLast(data);
return;
}
Node preNode = search(idx - 1);
Node postNode = preNode.nextNode;
Node newNode = new Node(data);
preNode.nextNode = newNode;
newNode.nextNode = postNode;
size++;
}
// 맨 앞에 삭제
public Object removeFirst() {
if (size == 0) {
return null;
}
Node headNode = head;
head = head.nextNode;
tail.nextNode = head;
size--;
if (size == 0) {
head = null;
tail = null;
}
return headNode.data;
}
// 맨 뒤에 삭제
public Object removeLast() {
if (size <= 1) {
return removeFirst();
}
Node secondLastNode = search(size - 2);
Node lastNode = tail;
tail = secondLastNode;
tail.nextNode = head;
size--;
return lastNode.data;
}
// 중간에 삭제
public Object remove(int idx) {
if (idx == 0) {
return removeFirst();
}
if (idx == size - 1) {
return removeLast();
}
Node preNode = search(idx - 1);
Node lastNode = preNode.nextNode;
preNode.nextNode = preNode.nextNode.nextNode;
size--;
return lastNode.data;
}
// string으로 데이터 출럭
public String toString() {
StringBuffer str = new StringBuffer("[");
Node node = head;
if (node != null) {
str.append(node.data);
node = node.nextNode;
while (node != null && node != head) {
str.append(", ");
str.append(node.data);
node = node.nextNode;
}
}
str.append("]");
return str.toString();
}
public static void main(String[] args) {
CircularLinkedList linkedList = new CircularLinkedList();
// 맨 앞에 추가
linkedList.addFirst(1);
linkedList.addFirst(2);
linkedList.addFirst(3);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 1]
// 맨 뒤에 추가
linkedList.addLast(4);
linkedList.addLast(5);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 1, 4, 5]
// 중간에 추가
linkedList.add(10, 2);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 10, 1, 4, 5]
// 맨 앞에 삭제
linkedList.removeFirst();
System.out.println(linkedList.toString()); // 출력 : [2, 10, 1, 4, 5]
// 맨 뒤에 삭제
linkedList.removeLast();
System.out.println(linkedList.toString()); // 출력 : [2, 10, 1, 4]
// 중간에 삭제
linkedList.remove(2);
System.out.println(linkedList.toString()); // 출력 : [2, 10, 4]
}
}
public class DoublyLinkedList {
Node head;
Node tail;
int size;
public DoublyLinkedList() {
this.head = null;
this.tail = null;
size = 0;
}
class Node {
Object data;
Node preNode;
Node postNode;
Node(Object data){
this.data = data;
this.preNode = null;
this.postNode = null;
}
}
// 특정 노드 위치 검색
public Node search(int idx) {
Node findNode = head; // 머리부터 시작함
for(int i = 0; i < idx; i++) {
findNode = findNode.postNode;
}
return findNode;
}
// 맨 앞에 추가
public void addFirst(Object data) {
Node newNode = new Node(data);
newNode.postNode = head;
if (head != null) {
head.preNode = newNode;
}
head = newNode;
if (head.postNode == null) {
tail = head;
}
size++;
}
// 맨 뒤에 추가
public void addLast(Object data) {
Node newNode = new Node(data);
if (size == 0) {
addFirst(data);
return;
}
tail.postNode = newNode;
newNode.preNode = tail;
tail = newNode;
size++;
}
// 중간에 추가
public void add(Object data, int idx) {
if (idx == 0) {
addFirst(data);
return;
}
if (idx == size) {
addLast(data);
return;
}
Node leftNode = search(idx - 1);
Node rightNode = leftNode.postNode;
Node newNode = new Node(data);
leftNode.postNode = newNode;
rightNode.preNode = newNode;
newNode.preNode = leftNode;
newNode.postNode = rightNode;
size++;
}
// 맨 앞에 삭제
public Object removeFirst() {
Node headNode = head;
head = head.postNode;
if (head == null) {
tail = null;
}
else {
head.preNode = null;
}
size--;
return headNode.data;
}
// 맨 뒤에 삭제
public Object removeLast() {
if (size <= 1) {
return removeFirst();
}
Node secondNode = search(size - 2);
Node lastNode = tail;
tail = secondNode;
tail.postNode = null;
size--;
return lastNode.data;
}
// 중간에 삭제
public Object remove(int idx) {
if (idx == 0) {
return removeFirst();
}
if (idx == size - 1) {
return removeLast();
}
Node leftNode = search(idx - 1);
Node lastNode = leftNode.postNode;
Node rightNode = lastNode.postNode;
leftNode.postNode = rightNode;
rightNode.preNode = leftNode;
size--;
return lastNode.data;
}
// string으로 데이터 출럭
public String toString() {
StringBuffer str = new StringBuffer("[");
Node node = head;
if (node != null) {
str.append(node.data);
node = node.postNode;
while(node != null) {
str.append(", ");
str.append(node.data);
node = node.postNode;
}
}
str.append("]");
return str.toString();
}
// string으로 데이터 거꾸로 출럭
public String toBackString() {
StringBuffer str = new StringBuffer("[");
Node node = tail;
if (node != null) {
str.append(node.data);
node = node.preNode;
while(node != null) {
str.append(", ");
str.append(node.data);
node = node.preNode;
}
}
str.append("]");
return str.toString();
}
public static void main(String[] args) {
DoublyLinkedList linkedList = new DoublyLinkedList();
// 맨 앞에 추가
linkedList.addFirst(1);
linkedList.addFirst(2);
linkedList.addFirst(3);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 1]
// 맨 뒤에 추가
linkedList.addLast(4);
linkedList.addLast(5);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 1, 4, 5]
// 중간에 추가
linkedList.add(10, 2);
System.out.println(linkedList.toString()); // 출력 : [3, 2, 10, 1, 4, 5]
// 맨 앞에 삭제
linkedList.removeFirst();
System.out.println(linkedList.toString()); // 출력 : [2, 10, 1, 4, 5]
// 맨 뒤에 삭제
linkedList.removeLast();
System.out.println(linkedList.toString()); // 출력 : [2, 10, 1, 4]
// 중간에 삭제
linkedList.remove(2);
System.out.println(linkedList.toString()); // 출력 : [2, 10, 4]
System.out.println(linkedList.toBackString()); // 거꾸로 - 출력 : [4, 10, 2]
}
}