โ รซยถโรชยณยผ รฌฦโฐรฌยโ รชยณยตรซยถโฌรญโขลรซโนยครชยณ รญโบลรซยฅยญรญโขล รญโขโรชยฐโฌรชยฐโฌ รซยหรฌยงโฌ รฌโขล รซโยฏ, รฌยปยดรญโยจรญโยฐรชยณยผรญโขโขรฌยโ รชยณยตรซยถโฌรญโขลรซโนยครชยณ รญโบลรซยฅยญรญโขล รญโโรซยกลรชยทยธรซลพหรซยจยธรชยฐโฌ รซยหรฌยงโฌรซล โ รฌโขล รซล โรซโนยค. โ
- Eric Raymond
รฌยยธรซยฅหรญโขโขรฌลพย, รฌหยครญโหรฌโ ลรฌล ยค รฌลกยดรซยโขรฌยห รซลโฌรญโล รฌโลรฌห รชยฐโฌ

Singly LinkedList ์๋ฃ๊ตฌ์กฐ
Singly Linkedlist(๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ) ํน์ง์ผ๋ก ๋ค์๊ณผ ๊ฐ์ด ์์ฝ์ด ๊ฐ๋ฅํ๋ค.
- ๋ ธ๋(๊ฐ์ฒด)๋ฅผ ์ฐ๊ฒฐํ์ฌ ๋ฆฌ์คํธ ์ฒ๋ผ ๋ง๋ ์ปฌ๋ ์ (๋ฐฐ์ด์ด ์๋)
- ๋ฐ์ดํฐ์ ์ค๊ฐ ์ฝ์ , ์ญ์ ๊ฐ ๋น๋ฒํ ๊ฒฝ์ฐ ๋น ๋ฅธ ์ฑ๋ฅ์ ๋ณด์ฅํ๋ค.
- ํ์ง๋ง ์์์ ์์์ ๋ํ ์ ๊ทผ ์ฑ๋ฅ์ ์ข์ง ์๋ค.
- ํนํ Singly Linked List๋ ๋จ๋ฐฉํฅ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ด๊ธฐ ๋๋ฌธ์ ๋ง์ผ ๋ฆฌ์คํธ์ ๋ ์์๋ฅผ ํ์ํ๋ ค๋ฉด, ์ฒ์(head)๋ถํฐ ๋๊น์ง ์ํํ๋ฉฐ ํ์ํด์ผ ํ๊ธฐ ๋๋ฌธ์ ๊ต์ฅํ ํจ์จ์ด ๋จ์ด์ง๋ค. (์ด๋ฅผ ๊ฐ์ ํ ๊ฒ์ด Doubly Linked List)
- ์ด๋ฐ์ ๋ฐ์ดํฐ์ ์ ์ฅ์์๊ฐ ์ ์ง๋๊ณ ์ค๋ณต์ ํ์ฉํ๋ค.

[JCF] ๐งฑ LinkedList ๊ตฌ์กฐ & ์ฌ์ฉ๋ฒ - ์ ๋ณตํ๊ธฐ
LinkedList ์ปฌ๋ ์ ์๋ฐ์ Linked List๋ ArrayList์ ๊ฐ์ด ์ธ๋ฑ์ค๋ก ์ ๊ทผํ์ฌ ์กฐํ / ์ฝ์ ์ด ๊ฐ๋ฅํ์ง๋ง ๋ด๋ถ ๊ตฌ์กฐ๋ ์์ ํ ๋ค๋ฅด๊ฒ ๊ตฌ์ฑ๋์ด ์๋ค๋ ์ ์ด ํน์ง์ด๋ค. ArrayList๋ ๋ด๋ถ์ ์ผ๋ก ๋ฐฐ์ด์ ์ด์ฉํ
inpa.tistory.com
Singly LinkedList ์ค์ ๊ตฌํํ๊ธฐ
์ฐ์ ๋ณธ ๊ฐ์์์ Singly LinkedList์ ๋ชจ๋ ๋ฉ์๋ ๊ธฐ๋ฅ์ ๊ตฌํํ์ง ์๋๋ค.
Singly LinkedList๋ ์๋ฃ ๊ตฌ์กฐ ํ๊ณ์ ํ์ ์ฑ๋ฅ์ด ์ข์ง ๋ชปํ๊ธฐ ๋๋ฌธ์ ํ์ ์์ ์ ์ฐ์ด์ง ์์ผ๋ฉฐ, ์ค์ ๋ก ์๋ฐ์ LinkedList ํด๋์ค๋ ๋ด๋ถ์์๋ Doubly LinkedList๋ก ๊ตฌํ๋์ด ์๋ค.
๋ค๋ง, Doubly LinkedList์ ์๋ ์๋ฆฌ๋ฅผ ์๊ธฐ ์ํด์ ์ ์ ์ง์์ผ๋ก Singly LinkedList์ ์๋ ์๋ฆฌ ๋ถํฐ ์ดํดํด์ผ ๋์ค์ ์๋ฐฉํฅ ์ฐ๊ฒฐ ๊ตฌ์กฐ๋ฅผ ์ดํดํ๊ธฐ ์ฉ์ดํ๋ค. ๋ฐ๋ผ์ Singly LinkedList๋ add, remove ๊ทธ๋ฆฌ๊ณ get, set ๊ธฐ๋ฅ ์ ๋๋ง ๊ตฌํํ์ฌ ๊ฐ์ฒด๊ฐ์ ๋งํฌ๋ ๊ตฌ์กฐ ์๋ฆฌ ์ ๋๋ง ํ์ ํด๋ณผ ๊ฒ์ด๋ค.
ํด๋์ค ํ๋ & ์์ฑ์ ์ ์ํ๊ธฐ
public class MySinglyLinkedList<E> {
private Node<E> head; // ๋
ธ๋์ ์ฒซ ๋ถ๋ถ์ ๊ฐ๋ฆฌํค๋ ํฌ์ธํธ
private Node<E> tail; // ๋
ธ๋์ ๋ง์ง๋ง ๋ถ๋ถ์ ๊ฐ๋ฆฌํค๋ ํฌ์ธํธ
private int size; // ์์ ๊ฐฏ์
public MySinglyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
- head : ๋ฆฌ์คํธ์ ๊ฐ์ฅ ์ฒซ ๋ ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํธ๋ก ์ด์ฉ๋ ๋ณ์
- tail : ๋ฆฌ์คํธ์ ๊ฐ์ฅ ๋ง์ง๋ง ๋ ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ํฌ์ธํธ๋ก ์ด์ฉ๋ ๋ณ์
- size : ๋ฆฌ์คํธ์ ์๋ ์์์ ๊ฐ์(์ฐ๊ฒฐ ๋ ๋ ธ๋์ ๊ฐ์)
head ์ tail ๊ฐ๋ ์ด ํ์ํ ์ด์

๊ทธ๋ฅ ๋
ธ๋๋ง next๋ก ์๋ก ์ฐธ์กฐํ์ฌ ์ฐ๊ฒฐํ๋ฉด ๋์ง head์ tail์ด๋ผ๋ ๊ฐ๋
์ด ํ์ํ ์ด์ ๋ ๊ฐ์ฅ ์ฒ์ ์์์ ๊ฐ์ฅ ๋ง์ง๋ง ์์์ ๋ํ ๋งํฌ๋ฅผ ํํํ๊ธฐ ์ํด์์ด๋ค. ํ๋์ ๋
ธ๋๋ ๋ค์ ๋
ธ๋ ์ ๋ณด๋ง ๊ฐ์ง๊ณ ์๊ธฐ ๋๋ฌธ์, ๊ฐ์ฅ ์ฒซ๋ฒ์งธ ๋
ธ๋๋ฅผ ์ฐธ์กฐํ๊ณ ์๋ ํฌ์ธํธ๋ฅผ ๋ง๋คํ์๊ฐ ์๊ณ ๊ทธ๊ฒ์ด head์ด๋ค. ๋ง์ง๋ง ๋
ธ๋๋ tail ์ด๋ค.
๋ํ ๋ค์์ ๋ฐฐ์ธ addLast() ๋ฉ์๋ ๊ฐ์๊ฒฝ์ฐ ์์๋ฅผ ๋งจ๋ง์ง๋ง์ ์ถ๊ฐํด์ค๋ tail์ด ์๋ค๋ฉด add ํ ๋๋ง๋ค ๋งจ๋ง์ง๋ง ์์๊ฐ ์ด๋๊น์ง์ธ์ง ์๊ธธ์ด ์๊ธฐ ๋๋ฌธ์ ๋งจ๋ ๋
ธ๋๋ค์ ์ฒ์ ๋ถํฐ ์ํํด์ผ ํ ์ง๋ ๋ชจ๋ฅธ๋ค.
๋ ธ๋ ํด๋์ค ์ ์ํ๊ธฐ
LinkedLIst์ ๊ฒฝ์ฐ ArrayList์ ๊ฐ์ฅ ํฐ ์ฐจ์ด์ ์ด๋ผ ํ๋ค๋ฉด ๋ฐ๋ก '๋
ธ๋(Node)'๋ผ๋ ์ ์ฅ์๋ฅผ ์ด์ฉํ์ฌ ์ฐ๊ฒฐํ๋ค๋ ์ ์ด๋ค. ๋
ธ๋๋ ๋๋จํ ๊ฑด ์๋๊ณ ๊ทธ๋ฅ ๊ฐ์ฒด ์ด๋ค. ์ด ํด๋์ค์๋ ์๋ฃ๋ฅผ ์ ์ฅํ Data ๋ผ๋ ํ๋์ ๋ค์ ์ฐ๊ฒฐ ์์์ ์ฃผ์๋ฅผ ์ ์ฅํ๋ Next ๋ผ๋ ํ๋๋ฅผ ๊ฐ์ง๊ณ ์์ ๋ฟ์ด๋ค.

๊ทธ๋ฆฌ๊ณ ์ด ๋ ธ๋ ๊ฐ์ฒด๋ค์ด ์๋ก ์ฐ๊ฒฐ๋ ํํ๊ฐ Linked List ์ธ ๊ฒ์ด๋ค.
์ ์๊ฐ์ ๊ตฌํํด๋ณธ ArrayList์ ๊ฒฝ์ฐ ์ค๋ธ์ ํธ ๋ฐฐ์ด(Object[])์ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ๋ฅผ ๋ด์๋์๋ค๋ฉด, LinkedList ๋ ์ฌ๋ฌ ๋
ธ๋ ๊ฐ์ฒด๋ค์ ๋ด๋ถ์ ์ธ ์ฒ๋ฆฌ๋ก ์ฒด์ธ(chain)์ฒ๋ผ ์ฐ๊ฒฐํ๋ค.
public class MySinglyLinkedList<E> {
// ...
// inner static class
private static class Node<E> {
private E item; // Node์ ๋ด์ ๋ฐ์ดํฐ
private Node<E> next; // ๋ค์ Node ๊ฐ์ฒด๋ฅผ ๊ฐ๋ฅดํค๋ ๋ํผ๋ฐ์ค
// ์์ฑ์
Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
}
์ฌ๊ธฐ์ ๋์ฌ๊ฒจ ๋ด์ผ ํ ์ ์ ์ธ๊ฐ์ง ์ด๋ค.
- ์ ํด๋์ค ์์๋ค ํด๋์ค๋ฅผ ์ ์ธํ์๋๊ฐ?
- ์ private ์ ๊ทผ ์ง์์์ธ๊ฐ?
- ์ static์ด ๋ถ์๋๊ฐ?
๋ฌผ๋ก Node ํด๋์ค๋ฅผ MySinglyLinkedList ํด๋์ค ๋ฐ์์ ์ ์ธํด๋ ๋ฌธ์ ๋ ์๋ค. ๋ค๋ง Node ํด๋์ค๋ ์ค๋ก์ง MySinglyLinkedList ํด๋์ค์์๋ง ์ด์ฉ๋๋ฉฐ, ๋ค๋ฅธ ํด๋์ค์์๋ ์ ํ ์ด์ฉ๋์ง ์๋๋ค.
์ด๋ ๋ด๋ถ ํด๋์ค๋ก ์ ์ธํด์ฃผ๋ฉด ์ฌ๋ฌ๊ฐ์ง ์ฅ์ ์ ์ป๊ฒ ๋๋๋ฐ, ์ด์ ๋ํด์ ๋ด๋ถ ํด๋์ค์ ์ฅ์ ํฌ์คํ ์ ์ฐธ๊ณ ํ๊ธธ ๋ฐ๋๋ค. ๊ทธ๋ฆฌ๊ณ private ์ ๊ทผ์ ์ด์์ ๊ฒฝ์ฐ ๊ฐ์ฒด๊ฐ ์ธ๋ถ๋ก ๋ ธ์ถ๋๋ฉด ๋ณด์์์ ๋ฌธ์ ๊ฐ ๋ฐ์ํ ์ ์๊ธฐ ๋๋ฌธ์ ์ค๋ก์ง MySinglyLinkedList ๋ฉ์๋๋ก๋ง ์ ์ด๊ฐ ๊ฐ๋ฅํ๋๋ก ํ๊ธฐ์ํด ์ค์ ๋์๋ค.
๋ง์ง๋ง์ผ๋ก ๋ด๋ถ ํด๋์ค๋ฉด ๋ด๋ถ ํด๋์ค์ง static์ผ๋ก ์ ์ธํ ์ด์ ๋ ๋ฉ๋ชจ๋ฆฌ ํญ๋ฐ(memory leak) ์ด์ ๋๋ฌธ์ ๊ทธ๋ ๋ค. ์ด์ ๋ํด์ ๋ด๋ถ ํด๋์ค๋ static ์ผ๋ก ์ ์ธํ๋ผ ํฌ์คํ ์ ์ฐธ๊ณ ํ๊ธธ ๋ฐ๋๋ค.
search ๊ตฌํํ๊ธฐ
add์ remove๋ฅผ ๊ตฌํํ๊ธฐ ์์ ๋ฐ๋ก ๋ด๋ถ ๋ฉ์๋ ์ฉ์ผ๋ก search()๋ฅผ ๊ตฌํํ๊ณ ์ ํ๋ค.
add์ remove๋ฅผ ํ๊ธฐ ์ํด์ ์ฐ์ ์ถ๊ฐ / ์ญ์ ํ ์์ ํ์์ด ์ฐ์ ์ด ๋๊ธฐ ๋๋ฌธ์ ๋ฐ๋ณต์ ์ผ๋ก ์ฌ์ฌ์ฉ๋์ด ๋ฐ๋ก ๋ฉ์๋๋ก ๋บ๋ค.
๋งํฌ๋ ๋ฆฌ์คํธ์ ๊ฒ์์ ๊ฒฝ์ฐ ์ธ๋ฑ์ค๊ฐ ์๊ธฐ์ ๋๋ค ์์ธ์ค๋ฅผ ํ ์ ์๋ค. ๋ฐ๋ผ์ N๊ฐ์ ๋ ธ๋๋ฅผ ๊ฐ์ง๊ณ ์๋ ๋ ธ๋๋ฅผ ๊ฒ์ํ ๋, ์๊ฐ๋ณต์ก๋๋ O(N) ์ด ๋๊ฒ๋๋ค.
private Node<E> search(int index) {
// head(์ฒ์ ์์น) ์๋ถํฐ ์ฐจ๋ก๋ก index ๊น์ง ๊ฒ์
Node<E> n = head;
for (int i = 0; i < index; i++) {
n = n.next; // next ํ๋์ ๊ฐ(๋ค์ ๋
ธ๋ ์ฃผ์)๋ฅผ ์ฌ๋์
ํ๋ฉด์ ์์ฐจ์ ์ผ๋ก ์์๋ฅผ ํ์
}
return n;
}
์ด๋ ๋ฐ๋ณต๋ฌธ ๋ฒ์๋ฅผ index ๊น์ง ํ์์ด ์๋ index ์ ๊น์ง๋ง ํ์๋์ด์ผ ํ๋๋ฐ i < index , ์ด์ ๋ ๋
ธ๋์ next ํ๋ ์์ฒด๊ฐ ๊ทธ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๊ธฐ ๋๋ฌธ์ด๋ค.
add ๊ตฌํํ๊ธฐ
์๋ฐ์ LinkedList ํด๋์ค์ add ๋ฉ์๋ ์ข ๋ฅ๋ฅผ ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์ด 4๊ฐ์ง๊ฐ ์กด์ฌํ๋ค.
- void addFirst(Object obj) : ์ฒซ๋ฒ์งธ ์์น์ ์์ ์ถ๊ฐ
- void addLast(Objec obj) : ๋ง์ง๋ง ์์น์ ์์ ์ถ๊ฐ
- boolean add(Object obj) : ๋ง์ง๋ง ์์น์ ์์ ์ถ๊ฐ (์ฑ๊ณตํ๋ฉด true)
- void add(int index, Object element) : ์ง์ ๋ ์์น์ ์์ ์ถ๊ฐ
addFirst ๊ตฌํ
public void addFirst(E value) {
// 1. ๋จผ์ ๊ฐ์ฅ ์์ ์์๋ฅผ ๊ฐ์ ธ์ด
Node<E> first = head;
// 2. ์ ๋
ธ๋ ์์ฑ (์ด๋ ๋ฐ์ดํฐ์ next ํฌ์ธํธ๋ฅผ ์ค๋ค)
Node<E> newNode = new Node<>(value, first);
// 3. ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ size๋ฅผ ๋๋ฆฐ๋ค
size++;
// 4. ๋งจ์์ ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ head๋ฅผ ์
๋ฐ์ดํธํ๋ค
head = newNode;
// 5. ๋ง์ผ ์ต์ด๋ก ์์๊ฐ add ๋ ๊ฒ์ด๋ฉด head์ tail์ด ๊ฐ๋ฆฌํค๋ ์์๋ ๊ฐ๊ฒ ๋๋ค.
if (first == null) {
tail = newNode;
}
}
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์์๊ฐ ์ฒซ๋ฒ์งธ์ ์ถ๊ฐ๋๋ ๊ณผ์ ์ ๊ทธ๋ฆผ์ผ๋ก ๋ํ๋ด๋ณด์๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
1. head์ ๊ฐ(@100 ๋ฒ์ง ๊ฐ์ฒด)์ first ๋ณ์์ ๋ฐฑ์

2. ์ ๋ ธ๋๋ฅผ ์ถ๊ฐํ๋ฉด์ ์์๊ฐ๊ณผ tmp๊ฐ(@100)๋ฅผ ๋ฃ์ด ์ด๊ธฐํ ๋ฐ ๋ค์ ์์๋ก ์ฐ๊ฒฐ

3. head๋ฅผ ์ ๋ ธ๋๋ฅผ ๋ฐ๋ผ๋ณด๋๋ก ์ ๋ฐ์ดํธ (@100 โ @105)

๋ง์ผ ์ต์ด์ ์์๋ฅผ ์ถ๊ฐํ๋ ๊ฒ์ด๋ผ๋ฉด head์ tail์ด ํ๋์ ๊ฐ์ฒด๋ฅผ ๋ฐ๋ผ๋ณด๋๋ก ์ค์ ํ๋ ๊ฒ์ ์์ง ๋ง์.
1. head๊ฐ null ์ผ ๊ฒฝ์ฐ

2. head์ tail์ด ์ต์ด๋ก ์ถ๊ฐ๋ ์ ๋ ธ๋๋ฅผ ๋ฐ๋ผ๋ณด๋๋ก ์ ๋ฐ์ดํธ

addLast ๊ตฌํ
public void addLast(E value) {
// 1. ๋จผ์ ๊ฐ์ฅ ๋ค์ ์์๋ฅผ ๊ฐ์ ธ์ด
Node<E> last = tail;
// 2. ์ ๋
ธ๋ ์์ฑ (๋งจ ๋ง์ง๋ง ์์ ์ถ๊ฐ๋๊น next ๋ null์ด๋ค)
Node<E> newNode = new Node<>(value, null);
// 3. ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ size๋ฅผ ๋๋ฆฐ๋ค
size++;
// 4. ๋งจ๋ค์ ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ tail๋ฅผ ์
๋ฐ์ดํธํ๋ค
tail = newNode;
if (last == null) {
// 5. ๋ง์ผ ์ต์ด๋ก ์์๊ฐ add ๋ ๊ฒ์ด๋ฉด head์ tail์ด ๊ฐ๋ฆฌํค๋ ์์๋ ๊ฐ๊ฒ ๋๋ค.
head = newNode;
} else {
// 6. ์ต์ด ์ถ๊ฐ๊ฐ ์๋๋ผ๋ฉด last ๋ณ์(์ถ๊ฐ ๋๊ธฐ ์ ๋ง์ง๋ง์ด์๋ ์์)์์ ์ถ๊ฐ๋ ์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์
๋ฐ์ดํธ
last.next = newNode;
}
}
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์์๊ฐ ๋ง์ง๋ง์ ์ถ๊ฐ๋๋ ๊ณผ์ ์ ๊ทธ๋ฆผ์ผ๋ก ๋ํ๋ด๋ณด์๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
1. last ๋ณ์์ ํ์ฌ ๋ง์ง๋ง ์์(@300)๋ฅผ ๋ฐฑ์

2. ์ ๋ ธ๋๋ฅผ ์ถ๊ฐํ๊ณ tail์ ์ ๋ฐ์ดํธ

3. ์์๊ฐ ์ถ๊ฐ๋๊ธฐ ์ด์ ์ ์์(last ๋ณ์)์์ next๋ฅผ ์ ๋ฐ์ดํธ (null โ @400)

add ๊ตฌํ
add()์ ๋์์ addLast() ์ ๊ฐ๋ค. ์ค์ ๋ก LinkedLIst API๋ฅผ ๋ณด๋ฉด add ๋ฉ์๋๋ฅผ ํธ์ถํ๋ฉด addLast()๋ฅผ ํธ์ถํ๋ค.
public boolean add(E value) {
addLast(value);
return true;
}
add ์ค๊ฐ ์ฝ์ ๊ตฌํ
- ๋ฆฌ์คํธ ์ค๊ฐ์ ์ฝ์ ํ๊ธฐ ์ํด์ ๊ฐ์ฅ ๋จผ์ ์ธ๋ฑ์ค ๋ฒ์๋ฅผ ์ฒดํฌํด์ผ ํ๋ค.
- ์ธ๋ฑ์ค๊ฐ ์ฒ์๊ณผ ๋์ด๋ฉด ์์์ ๊ตฌํํ addFirst, addLast๋ฅผ ์ฌํ์ฉํ๋ฉด ๋๋ค.
- ์ถ๊ฐํ๋ ค๋ ์์น๋ฅผ ๊ตฌํ๊ธฐ ์ํด ์์์ ๊ตฌํํ search ๋ฉ์๋๋ฅผ ์ด์ฉํ๋ค.
- ์ด์ ๋ ธ๋(prev_node) ์ ๋ค์ ๋ ธ๋(next_node) ์ฐธ์กฐ๊ฐ์ ๋ณ์์ ๋ฐฑ์ ํ๋ ๊ฒ์ด ํฌ์ธํธ์ด๋ค.
- prev_node์ next๋ new_node์ ์ฐ๊ฒฐ, new_node๋ next_node์ ์ฐ๊ฒฐ ์ํค๋๋ก ํจ์ผ๋ก์จ ์ฝ์ ์ด ์๋ฃ๋๋ค.
public void add(int index, E value) {
// 1. ์ธ๋ฑ์ค๊ฐ 0๋ณด๋ค ์๊ฑฐ๋ size ๋ณด๋ค ๊ฐ๊ฑฐ๋ ํด ๊ฒฝ์ฐ ์๋ฌ
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. ์ถ๊ฐํ๋ ค๋ index๊ฐ 0์ด๋ฉด addFirst ํธ์ถ
if (index == 0) {
addFirst(value);
return;
}
// 3. ์ถ๊ฐํ๋ ค๋ index๊ฐ size - 1์ ๊ฐ์ผ๋ฉด addLast ํธ์ถ
if (index == size - 1) {
addLast(value);
return;
}
// 4. ์ถ๊ฐํ๋ ค๋ ์์น์ ์ด์ ๋
ธ๋ ์ป๊ธฐ
Node<E> prev_node = search(index - 1);
// 5. ์ถ๊ฐํ๋ ค๋ ์์น์ ๋ค์ ๋
ธ๋ ์ป๊ธฐ
Node<E> next_node = prev_node.next;
// 6. ์ ๋
ธ๋ ์์ฑ (๋ฐ๋ก ๋ค์ ๋
ธ๋์ ์ฐ๊ฒฐ)
Node<E> newNode = new Node<>(value, next_node);
// 7. size ์ฆ๊ฐ
size++;
// 8. ์ด์ ๋
ธ๋๋ฅผ ์ ๋
ธ๋์ ์ฐ๊ฒฐ
prev_node.next = newNode;
}
๋ง์ผ index๊ฐ 1์ธ ์์น(@200๋ฒ์ง)์ ๋ ธ๋๋ฅผ ์ฝ์ ํ๋ค๊ณ ๊ฐ์ ํ๋ค๋ฉด add ์ค๊ฐ ์ฝ์ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ๋ค.
1. ์ถ๊ฐํ๋ ค๋ ์์น์ ์ด์ ๋ ธ๋(prev_node) ์ ๋ค์ ๋ ธ๋(next_node)๋ฅผ ์์ ์ ์ฅ

2. ์ ๋ ธ๋ ์์ฑ (์์ฑํ๋ฉฐ ๋ค์ ๋ ธ๋์ ์ฐ๊ฒฐ)

3. ์ด์ ๋ ธ๋์ ์ฐธ์กฐ๋ฅผ ์ถ๊ฐ๋ ์ ๋ ธ๋์ ์ฐ๊ฒฐ (@200 โ @150)

remove ๊ตฌํํ๊ธฐ
LinkedList์ remove ๋ฉ์๋์๋ ๋ค์๊ณผ ๊ฐ์ด ์ด 5๊ฐ์ง๊ฐ ์กด์ฌํ๋ค.
- Object removeFirst() : ๋งจ ์ ์์๋ฅผ ์ ๊ฑฐ (์ ๊ฑฐํ ์์๋ ๋ฐํ)
- Object remove() : ๋งจ ์ ์์๋ฅผ ์ ๊ฑฐ
- Object removeLast() : ๋งจ ๋ค ์์๋ฅผ ์ ๊ฑฐ
- Object remove(int index) : ์ธ๋ฑ์ค ์์น์ ์์๋ฅผ ์ ๊ฑฐ
- boolean remove(Object value) : ์์๊ฐ์ด ์ผ์นํ๋ ์์น์ ์์๋ฅผ ์ ๊ฑฐ (์ค๋ณต ์์๊ฐ์ด ์์ ๊ฒฝ์ฐ ๋งจ์์ ์์๊ฐ ์ ๊ฑฐ)
remove ์๋์๋ฆฌ๋ add ๋ฉ์ปค๋์ฆ์ ๋ฐ๋๋ก ์๊ฐํด์ ๊ตฌํํด์ฃผ๋ฉด ๋์ด ๊ทธ๋ฆฌ ์ด๋ ต์ง ์๋ค.
removeFirst ๊ตฌํ
public E removeFirst() {
// 1. ๋ง์ฝ ์ญ์ ํ ์์๊ฐ ์๋ฌด๊ฒ๋ ์์ผ๋ฉด ์๋ฌ
if (head == null) {
throw new IndexOutOfBoundsException();
}
// 2. ์ญ์ ๋ ์ฒซ๋ฒ์งธ ์์์ ๋ฐ์ดํฐ๋ฅผ ๋ฐฑ์
E returnValue = head.item;
// 3. ๋๋ฒ์งธ ๋
ธ๋๋ฅผ ์์ ์ ์ฅ
Node<E> first = head.next;
// 4. ์ฒซ๋ฒ์งธ ๋
ธ๋์ ๋ด๋ถ ์์๋ฅผ ๋ชจ๋ ์ญ์
head.next = null;
head.item = null;
// 5. head๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์
๋ฐ์ดํธ
head = first;
// 6. ์์๊ฐ ์ญ์ ๋์์ผ๋ ํฌ๊ธฐ ๊ฐ์
size--;
// 7. ๋ง์ผ ๋ฆฌ์คํธ์ ์ ์ผํ ๊ฐ์ ์ญ์ ํด์ ๋น ๋ฆฌ์คํธ๊ฐ ๋ ๊ฒฝ์ฐ, tail๋ null ์ฒ๋ฆฌ
if (head == null) {
tail = null;
}
// 8. ๋ง์ง๋ง์ผ๋ก ์ญ์ ๋ ์์๋ฅผ ๋ฐํ
return returnValue;
}
1. ๋ฐํํ ์ญ์ ํ ์ฒซ๋ฒ์งธ ์์ ๋ฐ์ดํฐ๋ฅผ ๋ฐฑ์ ํ๋ค.
2. ์ฒซ์งธ ์์๊ฐ ์ญ์ ๊ฐ ๋๋ฉด ๋๋ฒ์งธ ์์๊ฐ ์ฒซ์งธ๊ฐ ๋๊ธฐ ๋๋ฌธ์ ๋๋ฒ์งธ ์์๋ฅผ ๋ณ์ first์ ์ ์ฅํด์ ๋์ค์ ๋ค๋ฃจ๋๋ก ํ๋ค.

3. ์ฒซ๋ฒ์งธ ๋ ธ๋์ ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ null๋ก ์ฒ๋ฆฌํ๋ค.

4. head์ ํฌ์ธํธ๋ฅผ frist ๋ณ์์ ์ ์ฅํด๋์๋ ๋๋ฒ์งธ ๋ ธ๋(@200)์ผ๋ก ์ ๋ฐ์ดํธํ๋ค.
5. ์๋ฌด๊ฒ๋ ์ฐ๊ฒฐ๋์ง ์์ ๊ณ ์๊ฐ ๋๋ฒ๋ฆฐ ๋ ธ๋๋ ๋์ค์ GC๊ฐ ์๊ฑฐํด ๊ฐ๋ค.

์ถ๊ฐ์ ์ผ๋ก ๋ง์ผ ์ญ์ ํ ์์๊ฐ ๋ฆฌ์คํธ์ ์ ์ผํ ์์๋ผ๋ฉด, ์ญ์ ํ ์ ๋น ๋ฆฌ์คํธ๊ฐ ๋๋ฏ๋ก head์ tail์ null์ด ๋๋๋ก ์ ๋ฐ์ดํธ ํด์ค๋ค.



remove ๊ตฌํ
LinkedList์ ๊ธฐ๋ณธ remove() ๋์์ add()์ ๋ฌ๋ฆฌ ์ฒซ์งธ ์์๋ฅผ ์ฒ๋ฆฌํ๋ค.
public E remove() {
return removeFirst();
}
์ธ๋ฑ์ค๋ก remove ๊ตฌํ
public E remove(int index) {
// 1. ์ธ๋ฑ์ค๊ฐ 0๋ณด๋ค ์๊ฑฐ๋ size ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ๊ฒฝ์ฐ ์๋ฌ (size์ ๊ฐ์ ๊ฒฝ์ฐ ๋น ๊ณต๊ฐ์ ๊ฐ๋ฆฌํค๋ ๊ฑฐ๋๊น)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. ์ธ๋ฑ์ค๊ฐ 0์ด๋ฉด removeFirst ๋ฉ์๋ ์คํํ๊ณ ๋ฆฌํด
if (index == 0) {
return removeFirst();
}
// 3. ์ญ์ ํ ์์น์ ์ด์ ๋
ธ๋ ์ ์ฅ
Node<E> prev_node = search(index - 1);
// 4. ์ญ์ ํ ์์น์ ๋
ธ๋ ์ ์ฅ
Node<E> del_node = prev_node.next;
// 5. ์ญ์ ํ ์์น์ ๋ค์ ๋
ธ๋ ์ ์ฅ
Node<E> next_node = del_node.next;
// 6. ์ญ์ ๋ ์ฒซ๋ฒ์งธ ์์์ ๋ฐ์ดํฐ๋ฅผ ๋ฐฑ์
E returnValue = del_node.item;
// 7. ์ญ์ ๋
ธ๋์ ๋ด๋ถ ์์๋ฅผ ๋ชจ๋ ์ญ์
del_node.next = null;
del_node.item = null;
// 8. ์์๊ฐ ์ญ์ ๋์์ผ๋ ํฌ๊ธฐ ๊ฐ์
size--;
// 9. ์ด์ ๋
ธ๋๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์
๋ฐ์ดํธ
prev_node.next = next_node;
// 10. ๋ง์ง๋ง์ผ๋ก ์ญ์ ๋ ์์๋ฅผ ๋ฐํ
return returnValue;
}
1. ๋ง์ผ ์ธ๋ฑ์ค 1์ ์์๋ฅผ ์ญ์ ํ๋ค๊ณ ํ๋ฉด ๋จผ์ ์ญ์ ํ ์์น๋ฅผ ํ์ํ๋ค.
2. search ๋ฉ์๋์์ ๋ฐํํ ๋ ธ๋๋ฅผ ์ด์ฉํ์ฌ, ์ญ์ ํ๋ ค๋ ์์น์ ์ด์ ๋ ธ๋(prev_node) ์ ์ญ์ ๋ ธ๋(del_node) ๊ทธ๋ฆฌ๊ณ ๋ค์ ๋ ธ๋(next_node) ์ฐธ์กฐ๊ฐ์ ๋ณ์ 3๊ฐ์ ์ ์ฅํ๋ค.
3. ๋ฐํํ ๋ฐ์ดํฐ๋ฅผ ๋ฐฑ์ ํด๋๋ค.

4. del_node์ ๋ฐ์ดํฐ๋ฅผ ๋ชจ๋ ์ญ์ ํ๋ค.

5. prev_node์ next ๊ฐ์ next_node๋ก ์ฌ์ค์ ํ๋ค.

๊ฐ์ผ๋ก remove ๊ตฌํ
๊ฐ์ผ๋ก ์์๋ฅผ remove ํ๋ ๋ก์ง์ ์ฝ๊ฐ ๋ณต์กํ๋ค. ์๋ํ๋ฉด search() ๋ฉ์๋๋ฅผ ์ฌ์ฉํ ์ ์๊ธฐ ๋๋ฌธ์ ์ง์ ์ํ ์ ๋ต์ ๊ตฌ์ฑํด์ผ ๋๊ธฐ ๋๋ฌธ์ด๋ค.
public boolean remove(Object value) {
// 1. ๋ง์ฝ ์ญ์ ํ ์์๊ฐ ์๋ฌด๊ฒ๋ ์์ผ๋ฉด ์๋ฌ
if (head == null) {
throw new RuntimeException();
}
// 2. ์ด์ ๋
ธ๋, ์ญ์ ๋
ธ๋, ๋ค์ ๋
ธ๋๋ฅผ ์ ์ฅํ ๋ณ์ ์ ์ธ
Node<E> prev_node = null;
Node<E> del_node = null;
Node<E> next_node = null;
// 3. ๋ฃจํ ๋ณ์ ์ ์ธ
Node<E> i = head;
// 4. ๋
ธ๋์ next๋ฅผ ์ํํ๋ฉด์ ํด๋น ๊ฐ์ ์ฐพ๋๋ค.
while (i != null) {
if (Objects.equals(i.item, value)) {
// ๋
ธ๋์ ๊ฐ๊ณผ ๋งค๊ฐ๋ณ์ ๊ฐ์ด ๊ฐ์ผ๋ฉด ์ญ์ ๋
ธ๋์ ์์๋ฅผ ๋์
ํ๊ณ break
del_node = i;
break;
}
// Singly Linked List์๋ prev ์ ๋ณด๊ฐ ์๊ธฐ ๋๋ฌธ์ ์ด์ ๋
ธ๋์๋ ์์๋ฅผ ์ผ์ผํ ๋์
ํ์ฌ์ผ ํจ
prev_node = i;
i = i.next;
}
// 5. ๋ง์ผ ์ฐพ์ ์์๊ฐ ์๋ค๋ฉด ๋ฆฌํด
if (del_node == null) {
return false;
}
// 6. ๋ง์ฝ ์ญ์ ํ๋ ค๋ ๋
ธ๋๊ฐ head๋ผ๋ฉด, ์ฒซ๋ฒ์งธ ์์๋ฅผ ์ญ์ ํ๋ ๊ฒ์ด๋ removeFirst()๋ฅผ ์ฌ์ฉ
if (del_node == head) {
removeFirst();
return true;
}
// 7. ๋ค์ ๋
ธ๋์ ์ญ์ ๋
ธ๋ next์ ์์๋ฅผ ๋์
next_node = del_node.next;
// 8. ์ญ์ ์์ ๋ฐ์ดํฐ ๋ชจ๋ ์ ๊ฑฐ
del_node.next = null;
del_node.item = null;
// 9. ์์๊ฐ ์ญ์ ๋์์ผ๋ ํฌ๊ธฐ ๊ฐ์
size--;
// 10. ์ด์ ๋
ธ๋๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ์ฐธ์กฐํ๋๋ก ์
๋ฐ์ดํธ
prev_node.next = next_node;
return true;
}
removeLast ๊ตฌํ
์์์ ๊ตฌํํ remove(int index) ๋ฉ์๋๋ฅผ ์ฌํ์ฉํ์ฌ ๊ตฌํํ๋ค. ๋ฐ๋ผ์ ํ์ ์๊ฐ์ด ์์๋๊ธฐ ๋๋ฌธ์ removeFirst() ๋ณด๋ค๋ O(N) ์ ์๊ฐ์ด ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
addLast() ์ ๊ฐ์ด tail ์ ์ด์ฉํด์ ์์ ์๊ฐ์์ผ๋ก ์ฒ๋ฆฌ๋๋๋ก ๊ตฌํ ํ ๋ฒ ํ์ง๋ง, Singly Linked List๋ ๋
ธ๋ prev ๊ฐ๋
์ด ์๊ธฐ ๋๋ฌธ์ ์ญ์ ๋ ๋
ธ๋์ ์ด์ ์์๋ฅผ ์ฐธ์กฐํ ๋ฐฉ๋ฒ์ด ์์ด, ๊ฒฐ๊ตญ์ ์ฒ์ ๋ถํฐ ๋๊น์ง ์ํํด์ผ ํ๋ค๋ ๋จ์ ์ด ์กด์ฌํ๋ค.
public E removeLast() {
return remove(size - 1);
}
get ๊ตฌํํ๊ธฐ
์์์ ๊ตฌํํ search ๋ฉ์๋๋ก ๋ ธ๋๋ฅผ ๊ฒ์ํ์ฌ ๊ฐ์ ๋ฐํํ๋ฉด ๋๋ค.
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return search(index).item;
}
set ๊ตฌํํ๊ธฐ
public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 1. search ๋ฉ์๋๋ฅผ ์ด์ฉํด ๊ต์ฒดํ ๋
ธ๋๋ฅผ ์ป๋๋ค.
Node<E> replace_node = search(index);
// 2. ๊ต์ฒดํ ๋
ธ๋์ ์์๋ฅผ ๋ณ๊ฒฝํ๋ค.
replace_node.item = null;
replace_node.item = value;
}
toString ๊ตฌํํ๊ธฐ
๋ง์ง๋ง์ผ๋ก ๋งํฌ๋ ๋ฆฌ์คํธ ์์๋ค์ ์ถ๋ ฅํ๊ธฐ ์ํด Object ํด๋์ค์ toString() ๋ฉ์๋๋ฅผ ์ค๋ฒ๋ผ์ด๋ฉ ํ์.
์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ถ๋ ฅ์ ์ด๋ ต๊ฒ ์๊ฐํ ํ์ ์์ด, ๋ฐฐ์ด์ ๋ง๋ค๊ณ ๊ฐ ๋ฐฐ์ด ์ธ๋ฑ์ค ๋ง๋ค ๋ฆฌ์คํธ์ ๋ ธ๋ ์์๊ฐ์ ๋์ ํด ๋ณต์ฌ๋ฅผ ํ๋ค ๋ฌธ์์ด๋ก ๋ง๋ค์ด ๋ฐํํด์ฃผ๋ฉด ๋๋ค.
@Override
public String toString() {
// 1. ๋ง์ผ head ๊ฐ null ์ผ ๊ฒฝ์ฐ ๋น ๋ฐฐ์ด
if(head == null) {
return "[]";
}
// 2. ํ์ฌ size๋งํผ ๋ฐฐ์ด ์์ฑ
Object[] array = new Object[size];
// 3. ๋
ธ๋ next๋ฅผ ์ํํ๋ฉด์ ๋ฐฐ์ด์ ๋
ธ๋๊ฐ์ ์ ์ฅ
int index = 0;
Node<E> n = head;
while (n != null) {
array[index] = (E) n.item;
index++;
n = n.next;
}
// 3. ๋ฐฐ์ด์ ์คํธ๋งํํ์ฌ ๋ฐํ
return Arrays.toString(array);
}
์๋๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์ง์ ๋ฌธ์์ด ๋ํ๊ธฐ ์ฐ์ฐ์ผ๋ก๋ ๊ตฌํํด๋ ๋ฌธ์ ๋ ์๋ค.
@Override
public String toString() {
if(head == null) {
return "[]";
}
Node<E> n = head;
String result = "[";
while(n.next != null) {
result += n.item + ", ";
n = n.next;
}
// n์ด ๋ง์ง๋ง์ผ ๊ฒฝ์ฐ n.next๊ฐ null์ด๋ ๋ฃจํ๋ฌธ์ ๋น ์ ธ๋์ค๊ฒ ๋์ ๋ง์ง๋ง ๋
ธ๋ ์ฝ์
์ฒ๋ฆฌ๋ฅผ ํด์ฃผ์ด์ผ ํ๋ค.
result += n.item + "]";
return result;
}
LinkedList ๊ตฌํ ์ ์ฒด ์ฝ๋
์ง์ ์์ ์ด ๊ตฌํํ ์๋ฃ ๊ตฌ์กฐ ์๊ณ ๋ฆฌ์ฆ์ด ๋ฌธ์ ์์ด ๋์ํ๋์ง ๋ฉ์ธ ๋ฉ์๋์์ ํ ์คํธํ๋ ๊ฒ์ ์์ง๋ง์.
public class MySinglyLinkedList<E> {
private Node<E> head; // ๋
ธ๋์ ์ฒซ ๋ถ๋ถ์ ๊ฐ๋ฆฌํค๋ ํฌ์ธํธ
private Node<E> tail; // ๋
ธ๋์ ๋ง์ง๋ง ๋ถ๋ถ์ ๊ฐ๋ฆฌํค๋ ํฌ์ธํธ
private int size; // ์์ ๊ฐฏ์
public MySinglyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// inner static class
private static class Node<E> {
private E item; // Node์ ๋ด์ ๋ฐ์ดํฐ
private Node<E> next; // ๋ค์ Node ๊ฐ์ฒด๋ฅผ ๊ฐ๋ฅดํค๋ ๋ํผ๋ฐ์ค
// ์์ฑ์
Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
private Node<E> search(int index) {
// head(์ฒ์ ์์น) ์๋ถํฐ ์ฐจ๋ก๋ก index ๊น์ง ๊ฒ์
Node<E> n = head;
for (int i = 0; i < index; i++) {
n = n.next; // next ํ๋์ ๊ฐ(๋ค์ ๋
ธ๋ ์ฃผ์)๋ฅผ ์ฌ๋์
ํ๋ฉด์ ์์ฐจ์ ์ผ๋ก ์์๋ฅผ ํ์
}
return n;
}
public void addFirst(E value) {
// 1. ๋จผ์ ๊ฐ์ฅ ์์ ์์๋ฅผ ๊ฐ์ ธ์ด
Node<E> first = head;
// 2. ์ ๋
ธ๋ ์์ฑ (์ด๋ ๋ฐ์ดํฐ์ next ํฌ์ธํธ๋ฅผ ์ค๋ค)
Node<E> newNode = new Node<>(value, first);
// 3. ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ size๋ฅผ ๋๋ฆฐ๋ค
size++;
// 4. ๋งจ์์ ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ head๋ฅผ ์
๋ฐ์ดํธํ๋ค
head = newNode;
// 5. ๋ง์ผ ์ต์ด๋ก ์์๊ฐ add ๋ ๊ฒ์ด๋ฉด head์ tail์ด ๊ฐ๋ฆฌํค๋ ์์๋ ๊ฐ๊ฒ ๋๋ค.
if (first == null) {
tail = newNode;
}
}
public void addLast(E value) {
// 1. ๋จผ์ ๊ฐ์ฅ ๋ค์ ์์๋ฅผ ๊ฐ์ ธ์ด
Node<E> last = tail;
// 2. ์ ๋
ธ๋ ์์ฑ (๋งจ ๋ง์ง๋ง ์์ ์ถ๊ฐ๋๊น next ๋ null์ด๋ค)
Node<E> newNode = new Node<>(value, null);
// 3. ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ size๋ฅผ ๋๋ฆฐ๋ค
size++;
// 4. ๋งจ๋ค์ ์์๊ฐ ์ถ๊ฐ๋์์ผ๋ tail๋ฅผ ์
๋ฐ์ดํธํ๋ค
tail = newNode;
if (last == null) {
// 5. ๋ง์ผ ์ต์ด๋ก ์์๊ฐ add ๋ ๊ฒ์ด๋ฉด head์ tail์ด ๊ฐ๋ฆฌํค๋ ์์๋ ๊ฐ๊ฒ ๋๋ค.
head = newNode;
} else {
// 6. ์ต์ด ์ถ๊ฐ๊ฐ ์๋๋ผ๋ฉด last ๋ณ์(์ถ๊ฐ ๋๊ธฐ ์ ๋ง์ง๋ง์ด์๋ ์์)์์ ์ถ๊ฐ๋ ์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์
๋ฐ์ดํธ
last.next = newNode;
}
}
public void add(int index, E value) {
// 1. ์ธ๋ฑ์ค๊ฐ 0๋ณด๋ค ์๊ฑฐ๋ size ๋ณด๋ค ๊ฐ๊ฑฐ๋ ํด ๊ฒฝ์ฐ ์๋ฌ
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. ์ถ๊ฐํ๋ ค๋ index๊ฐ 0์ด๋ฉด addFirst ํธ์ถ
if (index == 0) {
addFirst(value);
return;
}
// 3. ์ถ๊ฐํ๋ ค๋ index๊ฐ size - 1์ ๊ฐ์ผ๋ฉด addLast ํธ์ถ
if (index == size - 1) {
addLast(value);
return;
}
// 4. ์ถ๊ฐํ๋ ค๋ ์์น์ ์ด์ ๋
ธ๋ ์ป๊ธฐ
Node<E> prev_node = search(index - 1);
// 5. ์ถ๊ฐํ๋ ค๋ ์์น์ ๋ค์ ๋
ธ๋ ์ป๊ธฐ
Node<E> next_node = prev_node.next;
// 6. ์ ๋
ธ๋ ์์ฑ (๋ฐ๋ก ๋ค์ ๋
ธ๋์ ์ฐ๊ฒฐ)
Node<E> newNode = new Node<>(value, next_node);
// 7. size ์ฆ๊ฐ
size++;
// 8. ์ด์ ๋
ธ๋๋ฅผ ์ ๋
ธ๋์ ์ฐ๊ฒฐ
prev_node.next = newNode;
}
public boolean add(E value) {
addLast(value);
return true;
}
@Override
public String toString() {
if (head == null) {
return "[]";
}
Node<E> n = head;
String result = "[";
while (n.next != null) {
result += n.item + ", ";
n = n.next;
}
// n์ด ๋ง์ง๋ง์ผ ๊ฒฝ์ฐ n.next๊ฐ null์ด๋ ๋ฃจํ๋ฌธ์ ๋น ์ ธ๋์ค๊ฒ ๋์ ๋ง์ง๋ง ๋
ธ๋ ์ฝ์
์ฒ๋ฆฌ๋ฅผ ํด์ฃผ์ด์ผ ํ๋ค.
result += n.item + "]";
return result;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return search(index).item;
}
public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 1. search ๋ฉ์๋๋ฅผ ์ด์ฉํด ๊ต์ฒดํ ๋
ธ๋๋ฅผ ์ป๋๋ค.
Node<E> replace_node = search(index);
// 2. ๊ต์ฒดํ ๋
ธ๋์ ์์๋ฅผ ๋ณ๊ฒฝํ๋ค.
replace_node.item = null;
replace_node.item = value;
}
public E removeFirst() {
// 1. ๋ง์ฝ ์ญ์ ํ ์์๊ฐ ์๋ฌด๊ฒ๋ ์์ผ๋ฉด ์๋ฌ
if (head == null) {
throw new RuntimeException();
}
// 2. ์ญ์ ๋ ์ฒซ๋ฒ์งธ ์์์ ๋ฐ์ดํฐ๋ฅผ ๋ฐฑ์
E returnValue = head.item;
// 3. ๋๋ฒ์งธ ๋
ธ๋๋ฅผ ์์ ์ ์ฅ
Node<E> first = head.next;
// 4. ์ฒซ๋ฒ์งธ ๋
ธ๋์ ๋ด๋ถ ์์๋ฅผ ๋ชจ๋ ์ญ์
head.next = null;
head.item = null;
// 5. head๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์
๋ฐ์ดํธ
head = first;
// 6. ์์๊ฐ ์ญ์ ๋์์ผ๋ ํฌ๊ธฐ ๊ฐ์
size--;
// 7. ๋ง์ผ ๋ฆฌ์คํธ์ ์ ์ผํ ๊ฐ์ ์ญ์ ํด์ ๋น ๋ฆฌ์คํธ๊ฐ ๋ ๊ฒฝ์ฐ, tail๋ null ์ฒ๋ฆฌ
if (head == null) {
tail = null;
}
// 8. ๋ง์ง๋ง์ผ๋ก ์ญ์ ๋ ์์๋ฅผ ๋ฐํ
return returnValue;
}
public E remove() {
return removeFirst();
}
public E remove(int index) {
// 1. ์ธ๋ฑ์ค๊ฐ 0๋ณด๋ค ์๊ฑฐ๋ size ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ๊ฒฝ์ฐ ์๋ฌ (size์ ๊ฐ์ ๊ฒฝ์ฐ ๋น ๊ณต๊ฐ์ ๊ฐ๋ฆฌํค๋ ๊ฑฐ๋๊น)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. ์ธ๋ฑ์ค๊ฐ 0์ด๋ฉด removeFirst ๋ฉ์๋ ์คํํ๊ณ ๋ฆฌํด
if (index == 0) {
return removeFirst();
}
// 3. ์ญ์ ํ ์์น์ ์ด์ ๋
ธ๋ ์ ์ฅ
Node<E> prev_node = search(index - 1);
// 4. ์ญ์ ํ ์์น์ ๋
ธ๋ ์ ์ฅ
Node<E> del_node = prev_node.next;
// 5. ์ญ์ ํ ์์น์ ๋ค์ ๋
ธ๋ ์ ์ฅ
Node<E> next_node = del_node.next;
// 6. ์ญ์ ๋ ์ฒซ๋ฒ์งธ ์์์ ๋ฐ์ดํฐ๋ฅผ ๋ฐฑ์
E returnValue = del_node.item;
// 7. ์ญ์ ๋
ธ๋์ ๋ด๋ถ ์์๋ฅผ ๋ชจ๋ ์ญ์
del_node.next = null;
del_node.item = null;
// 8. ์์๊ฐ ์ญ์ ๋์์ผ๋ ํฌ๊ธฐ ๊ฐ์
size--;
// 9. ์ด์ ๋
ธ๋๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์
๋ฐ์ดํธ
prev_node.next = next_node;
// 10. ๋ง์ง๋ง์ผ๋ก ์ญ์ ๋ ์์๋ฅผ ๋ฐํ
return returnValue;
}
public boolean remove(Object value) {
// 1. ๋ง์ฝ ์ญ์ ํ ์์๊ฐ ์๋ฌด๊ฒ๋ ์์ผ๋ฉด ์๋ฌ
if (head == null) {
throw new RuntimeException();
}
// 2. ์ด์ ๋
ธ๋, ์ญ์ ๋
ธ๋, ๋ค์ ๋
ธ๋๋ฅผ ์ ์ฅํ ๋ณ์ ์ ์ธ
Node<E> prev_node = null;
Node<E> del_node = null;
Node<E> next_node = null;
// 3. ๋ฃจํ ๋ณ์ ์ ์ธ
Node<E> i = head;
// 4. ๋
ธ๋์ next๋ฅผ ์ํํ๋ฉด์ ํด๋น ๊ฐ์ ์ฐพ๋๋ค.
while (i != null) {
if (Objects.equals(i.item, value)) {
// ๋
ธ๋์ ๊ฐ๊ณผ ๋งค๊ฐ๋ณ์ ๊ฐ์ด ๊ฐ์ผ๋ฉด ์ญ์ ๋
ธ๋์ ์์๋ฅผ ๋์
ํ๊ณ break
del_node = i;
break;
}
// Singly Linked List์๋ prev ์ ๋ณด๊ฐ ์๊ธฐ ๋๋ฌธ์ ์ด์ ๋
ธ๋์๋ ์์๋ฅผ ์ผ์ผํ ๋์
ํ์ฌ์ผ ํจ
prev_node = i;
i = i.next;
}
// 5. ๋ง์ผ ์ฐพ์ ์์๊ฐ ์๋ค๋ฉด ๋ฆฌํด
if (del_node == null) {
return false;
}
// 6. ๋ง์ฝ ์ญ์ ํ๋ ค๋ ๋
ธ๋๊ฐ head๋ผ๋ฉด, ์ฒซ๋ฒ์งธ ์์๋ฅผ ์ญ์ ํ๋ ๊ฒ์ด๋ removeFirst()๋ฅผ ์ฌ์ฉ
if (del_node == head) {
removeFirst();
return true;
}
// 7. ๋ค์ ๋
ธ๋์ ์ญ์ ๋
ธ๋ next์ ์์๋ฅผ ๋์
next_node = del_node.next;
// 8. ์ญ์ ์์ ๋ฐ์ดํฐ ๋ชจ๋ ์ ๊ฑฐ
del_node.next = null;
del_node.item = null;
// 9. ์์๊ฐ ์ญ์ ๋์์ผ๋ ํฌ๊ธฐ ๊ฐ์
size--;
// 10. ์ด์ ๋
ธ๋๊ฐ ๋ค์ ๋
ธ๋๋ฅผ ์ฐธ์กฐํ๋๋ก ์
๋ฐ์ดํธ
prev_node.next = next_node;
return true;
}
public E removeLast() {
return remove(size - 1);
}
}
public static void main(String[] args) {
MySinglyLinkedList<Number> l = new MySinglyLinkedList<>();
l.add(3);
l.add(6);
l.add(4);
l.add(3);
l.add(8);
l.add(10);
l.add(11);
System.out.println(l); // [3, 6, 4, 3, 8, 10, 11]
l.add(6, 100);
l.add(0, 101);
l.add(1, 102);
System.out.println(l); // [101, 102, 3, 6, 4, 3, 8, 10, 11, 100]
l.removeFirst();
l.removeFirst();
l.remove(1);
System.out.println(l); // [3, 4, 3, 8, 10, 11, 100]
l.remove(new Integer(3));
l.remove(new Integer(3));
System.out.println(l); // [4, 8, 10, 11, 100]
System.out.println(l.get(4)); // 100
l.set(4, 999);
System.out.println(l); // [4, 8, 10, 11, 999]
}

# ์ฐธ๊ณ ์๋ฃ
https://www.alphacodingskills.com/ds/linked-list.php
์ด ๊ธ์ด ์ข์ผ์ จ๋ค๋ฉด ๊ตฌ๋ & ์ข์์
์ฌ๋ฌ๋ถ์ ๊ตฌ๋
๊ณผ ์ข์์๋
์ ์์๊ฒ ํฐ ํ์ด ๋ฉ๋๋ค.