|
package com.popgene.datastructure;
/** * LinkedList의 노드 * @author eugene * */
public class Node { /** * data는 노드의 값 * next는 다음 노드 */
private Object data; private Node next;
/** * 최초 노드는 생설 될 때 다음 노드가 존재하지 않는다. * @param input 변수 값을 입력하면 data에 입력 */
public Node(Object input) { this.data = input; this.next = null; }
/* * 노드의 값을 출력하는 메쏘드. */ public String toString() { return String.valueOf(this.data); }
public void setData(Object data) { this.data = data; }
public Object getData() { return this.data; }
public void setNext(Node next) { this.next = next; }
public Node getNext() { return this.next; } } |
|
package com.popgene.datastructure;
/** * Linked List * @author eugene * */ public class LinkedList { /** * head는 첫 노드(헤드) * tail은 마지막 노드(테일) * size는 이 LinkedList의 크기 */ private Node head; private Node tail; private int size = 0;
/** * LinkedList의 맨 앞에 노드 추가 * @param input 추가될 노드의 값 * 현재의 헤드를 신규노드의 다음 노드로 설정 후, * LinkedList의 헤드를 신규 노드로 설정 * 헤드 노드를 생성했는데, 헤드노드의 다음 노드가 존재하지 않는다면(head.getNext() == null), * 헤드와 테일은 동일하다. * 신규노드 추가 후 LinkedList의 크기를 1 증가시켜준다. */ public void addFirst(Object input) { Node newNode = new Node(input); newNode.setNext(head); head = newNode; size++; if (head.getNext() == null) { tail = head; } }
/** * LinkedList의 끝에 노드 추가 * @param input * LinkedList의 크기가 0일 경우에는 addFirst를 통하여 노드 추가 * 신규 노드 생성 후 테일의 다음 노드를 신규노드로 설정 한 뒤 * 테일을 생성한 노드로 대체 */ public void addLast(Object input) { Node newNode = new Node(input); if(size == 0) { addFirst(input); } else { tail.setNext(newNode); tail = newNode; size++; } }
/** * 주어진 index의 위치의 노드를 조회 * @param index * @return Node * 헤드 노드부터 시작하여, index 전위치까지의 다음노드를 조회하는 방법으로 index위치의 노드를 조회 */ Node node(int index) { Node x = head; for (int i = 0; i < index; i++) x = x.getNext(); return x; }
/** * 특정위치에 노드 추가 * @param k * @param input * k위치에 input값의 노드를 추가 * 0번째에 추가면 addFirst 호출 * temp1 - node 메쏘드로 k - 1 위치의 노드를 조회, 삽입할 위치 바로 전 노드 * temp2 - temp1의 다음 노드를 가져옴 * temp1과 temp2 사이에 삽입 * 신규 노드를 생성하고 temp1의 다음 노드로 설정하고 신규노드의 다음 노드를 temp2로 설정 * LinkedList의 크기 증가 * 만약 신규노드의 다음이 없을 때, 신규노드를 테일로 설정 */ public void add(int k, Object input) { if (k==0) { addFirst(input); } else { Node temp1 = node(k-1); Node temp2 = temp1.getNext(); Node newNode = new Node(input); temp1.setNext(newNode); newNode.setNext(temp2); size++;
if (newNode.getNext() == null) { tail = newNode; } } }
/** * LinkedList의 모든 원소를 헤드부터 테일까지 순차적으로 출력 */ public String toString() { if (head==null) { return "[]"; }
Node temp = head; String str = "[";
while (temp.getNext() != null) { str += temp.getData() + ","; temp = temp.getNext(); }
str += temp.getData(); return str+"]"; }
/** * 헤드 노드 삭제 * @return Object * temp에 head를 넣고 head에 temp의 다음 노드를 넣은 후, returnData의 기존 헤드 노드의 값 보관 * temp 노드(기존 헤드 노드) null을 넣어 삭제, 기존 헤드 노드 값(returnData) 반환 * size 1 감소 */ public Object removeFirst() { Node temp = head; head = temp.getNext();
Object returnData = temp.getData(); temp = null; size--; return returnData; }
/** * k번째 노드 삭제 * @param k * @return Object * k가 0 즉 헤드 노드 삭제 시 removeFirst() 호출 * temp에 삭제할 전 노드를 node() 메쏘드로 조회하여 넣고, * todoDeleted에 삭제할 노드를 넣는다. * temp의 다음 노드를 현재 노드 다음 노드로 수정한다. * returnData에 삭제될 노드의 값을 넣는다. * 삭제될 노드가 테일일경우 테일을 삭제될 노드의 전 노드로 바꾼다. * 삭제될 노드(todoDeleted)를 null로 만들어 삭제한 후, LinkedList의 크기를 1 줄인다. * 삭제된 노드의 값을 반환한다. */ public Object remove(int k) { if(k == 0) return removeFirst(); Node temp = node(k-1); Node todoDeleted = temp.getNext(); temp.setNext(temp.getNext().getNext()); Object returnData = todoDeleted.getData();
if (todoDeleted == tail) { tail = temp; }
todoDeleted = null; size--; return returnData; }
/** * 마지막 노드 삭제 * @return Object * LinkedList 크기(size)에서 하나 전 위치로 remove() 메쏘드를 호출하여 삭제 */ public Object removeLast() { return remove(size-1); }
/** * LinkedList 크기 반환 * @return int */ public int size() { return size; }
/** * k번째 노드 값 반환 * @param k * @return Object */ public Object get(int k) { Node temp = node(k); return temp.getData(); }
/** * 값을 가지고 Node의 위치를 조회 * @param data * @return int */ public int indexOf(Object data) { Node temp = head; int index = 0; while (temp.getData() != data) { temp = temp.getNext(); index++; if (temp == null) return -1; }
return index; }
/** * 반복 * @return */ public ListIterator listIterator() { return new ListIterator(head); } } |
|
package com.popgene.datastructure;
public class ListIterator { /** * lastReturned: 이 ListIterator를 통해서 해당 LinkedList의 어느 노드까지 갔는 지를 나타내는 최근(마지막) 조회한 노드 * nextLink: lastReturned의 다음 노드, 즉 조회될 노드 * nextIndex: 조회될 노드의 위치 */
private Node lastReturned; private Node nextLink; private int nextIndex;
/** * @param head * ListIterator 생성 시 아직 조회 된 노드가 없으므로 lastReturned는 존재하지 않고 * 최초로 조회될 노드는 헤드 노드가 됨 */
ListIterator(Node head) { nextLink = head; nextIndex = 0; }
/** * 다음 노드 조회 * @return Object * 조회가 진행되면, lastReturned는 nextLink가 되고 * nextLink는 그 다음 노드가 된다. * nextIndex 1 증가 * 조회된 lastReturned의 값을 반환 */
public Object next() { lastReturned = nextLink; nextLink = nextLink.getNext(); nextIndex++;
return lastReturned.getData(); }
/** * LinkedList의 크기가 다음 위치 보다 작다면, 벗어 난 것이므로 다음 노드가 존재하지 않는다. * @param linkedListsize * @return boolean */
public boolean hasNext(int linkedListsize) { return nextIndex < linkedListsize; }
/** * 추가 * @param input * @param head * @return boolean * 새로운 노드를 생성하여, 마지막으로 조회된 노드(lastReturned)가 존재하지 않으면, 헤드에 새로운 노드를 넣고 * 새로운 노드의 다음 노드는 이 ListIterator의 현재 노드(nextLink)로 설정한다. * lastReturned가 존재하면, lastReturned의 뒤에 새로운 노드를 추가하고, 다음 조회할 노드가 새로운 노드의 다음노드가 된다. * 위 두가지 경우를 모두 거친 후 lastReturned를 새로운 노드로 설정하면, 새로운 노드 삽입이 끝난다. * nextIndex를 1 증가 */
public boolean add(Object input, Node head) { Node newNode = new Node(input);
if (lastReturned == null) { head = newNode; newNode.setNext(nextLink); } else { lastReturned.setNext(newNode); newNode.setNext(nextLink); }
lastReturned = newNode;
nextIndex++;
return true; }
/** * 삭제 * @param ll * ListIterator의 마지막으로 노드를 제거한다. * */
public void remove(LinkedList ll) { if (nextIndex == 0) { throw new IllegalStateException(); }
ll.remove(nextIndex-1);
nextIndex--; } } |
|
package com.popgene.datastructure;
public class LinkedListApp { public static void main(String[] args) { LinkedList numbers = new LinkedList(); numbers.addFirst(1); numbers.addFirst(0); numbers.addLast(10); numbers.addLast(15); numbers.addLast(20); numbers.add(0,40);
System.out.println("1:" + numbers);
numbers.remove(2);
System.out.println("2:" + numbers);
ListIterator li = numbers.listIterator();
Node ll = new Node(0);
while (li.hasNext(numbers.size())) { if ((int)li.next() == 1) li.remove(numbers); }
System.out.println("3:" + numbers);
li.add(3, ll);
System.out.println("4:" + numbers); } } |
이 프로그램에는 3개의 객체가 있다.
Node와 Node로 구성된 LinkeList, 그리고 LinkedList를 반복탐색하는 ListIterator.
설명은 주석으로 대체한다.
by 한국교통대 김지훈
| 번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
|---|---|---|---|---|
| 12 | Java 기초 - Parameter를 가진 메쏘드의 선언 | Eugene | 2025.04.16 | 34 |
| 11 | Java 기초 - 메쏘드를 가진 클래스의 선언과 클래스의 객체를 예시화(instantiate)하기 | Eugene | 2024.03.25 | 59 |
| 10 | Java Heap Sort(힙 정렬) | Eugene | 2022.04.12 | 309 |
| 9 | Java Max Heap(자바 맥스 힙) | Eugene | 2021.09.16 | 221 |
| 8 | Java - Binary Tree(자바 이진 트리) | Eugene | 2021.08.17 | 276 |
| 7 | Java Tree(자바 트리) - 자식 노드들을 리스트 자료구조를 사용하여 구현 | Eugene | 2021.04.01 | 2539 |
| » | JAVA Linked List(링크드 리스트) [1] | Eugene | 2021.02.09 | 792 |
| 5 | Java 기초 - 재귀 함수를 이용한 최대값 구하기 | Eugene | 2019.05.14 | 1101 |
| 4 | Java 기초 - while, for [2] | Eugene | 2018.04.05 | 860 |
| 3 | Java 기초 - 조건문 if | Eugene | 2017.11.03 | 757 |
| 2 | Java 기초 - 두 정수 입력 받아 합 구하기 | Eugene | 2017.11.01 | 3771 |
| 1 | Java 기초 - Hello, World! | Eugene | 2017.09.27 | 1780 |