[JAVA/자료구조]
LinkedList 링크드리스트 코드
및 알아보기
그림으로 알아보기
위와 같은 구조가 단순연결리스트 ( LinkedList ) 입니다.
삽입/삭제가 ArrayList보다 빠르다는 장점이 있습니다.
단점으로는 ArrayList는 무작위 접근이 가능하지만
LinkedList 에서는 순차접근만이 가능합니다.
왜그런지는
코드를 통해서 알아보도록 하겠습니다.
우선적으로 class를 만들어 줍니다.
이름은 LinkedList로 만들겠습니다.
public class LinkedList {
private Node head; // 맨 앞 정보를 가지고 있는 head 노드
private Node tail; // 맨 끝 정보를 가지고 있는 tail 노드
private int size = 0; // 노드의 크기 정보를 가지고 있는 변수
// 노드 선언 그림에서 O 가 되겠네요
private class Node {
private Object data; // 데이터를 가지고 있는 변수
private Node next; // 다음 노드 정보를 가지고 있는 변수
public Node(Object input) {
this.data = input; // 데이터 정보
this.next = null; // 다음 노드정보
}
public String toString() {
return String.valueOf(this.data);
}
}
// 맨 처음 노드를 생성하기위한 메소드
public void addFirst(Object input) {
Node newNode = new Node(input); // 노드 생성
// 새로운 노드는 head 정보를 가지고 있음
newNode.next = head;
head = newNode;
size++; // 사이즈를 늘려줌
if(head.next == null) {
tail = head;
}
}
// 맨 끝에 노드를 추가하기
public void addLast(Object input) {
Node newNode = new Node(input);
if(size == 0) {
addFirst(input);
} else {
tail.next = newNode; // 맨 끝 정보를 가지고 있도록 함
tail = newNode;
size++;
}
}
// 노드 추가하기
public void add(int k, Object input) {
if(k == 0) {
addFirst(input); // 맨 처음일 경우 addFirst 함수 실행
}else {
Node temp1 = node(k-1);
Node temp2 = temp1.next;
Node newNode = new Node(input);
temp1.next = newNode;
newNode.next = temp2;
size++;
if(newNode.next == null) {
tail = newNode;
}
}
}
// 맨처음 노드 삭제하기
public Object removeFirst() {
Node temp = head; // head 정보를 이용하여 삭제
head = head.next;
Object returnData = temp.data;
temp = null;
size--;
return returnData;
}
// 노드 삭제하기
public Object remove(int k) {
if(k == 0) {
return removeFirst();
}else {
Node temp = node(k-1);
Node todoDeleted = temp.next;
temp.next = todoDeleted.next;
Object returnData = todoDeleted.data;
if(todoDeleted == tail) {
tail = temp;
}
todoDeleted = null;
size--;
return returnData;
}
}
public Object removeLast() {
return remove(size-1);
}
// 크기 체크
public int size() {
return size;
}
// 노드정보를 가져오기
public Object get(int k) {
Node temp = node(k);
return temp.data;
}
// 데이터로 index 번호 알아오기
public int indexOf(Object inputdata) {
Node temp = head;
int index = 0;
while(temp.data != inputdata) {
temp = temp.next;
index++;
if(temp == null) {
return -1;
}
}
return index;
}
// 이터레이터
public ListIterator listIterator() {
return new ListIterator();
}
public String toString() {
if(head == null) {
return "[]";
}
Node temp = head;
String str = "[";
while(temp.next != null) {
str += temp.data + ", ";
temp = temp.next;
}
str += tail.data;
return str+"]";
}
Node node(int index) {
Node x = head;
for(int i=0; i < index; i++) {
x = x.next;
}
return x;
}
// 노드를 검색, 수정하기 위한 메소드
public class ListIterator{
private Node next;
private Node lastReturned;
private int nextIndex = 0;
ListIterator(){
next = head;
}
// 선택 노드 다음
public Object next() {
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.data;
}
public boolean hasNext() {
return nextIndex < size();
}
public void add(Object input) {
Node newNode = new Node(input);
if(lastReturned == null) {
head = newNode;
newNode.next = next;
}else {
lastReturned.next = newNode;
newNode.next = next;
}
lastReturned = newNode;
nextIndex++;
size++;
}
public void remove() {
if(nextIndex == 0) {
throw new IllegalStateException();
}
LinkedList.this.remove(nextIndex-1);
nextIndex--;
}
}
}
이제는 Main Class에서 LinkedList Class를 선언하여
사용하시면 되겠습니다.
이상으로 LinkedList를 코드로 알아보았습니다.
생활코딩 LinkedList를 참고하였습니다.
[JAVA/자료구조] LinkedList 링크드리스트 코드 및 알아보기
포스팅을 마치겠습니다.
