JAVA 手动实现LinkedList
节点
package com.ghg.data_structure.link;
public class Node<T> {
/**
* 数据
*/
public T data;
/**
* 前一个
*/
public Node pre;
/**
* 后一个
*/
public Node next;
public Node() {
super();
}
/**
*
* @param data 数据
* @param pre 前一个
*/
public Node(T data, Node pre, Node next) {
super();
this.data = data;
this.pre = pre;
this.next = next;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node getPre() {
return pre;
}
public void setPre(Node pre) {
this.pre = pre;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return data+" ";
}
}
List接口
package com.ghg.data_structure.link;
public interface MyList<T> {
/**
* 是否为空
* @return
*/
public boolean isEmpty();
/**
* 大小
* @return
*/
public int size();
/**
* 添加到第一个
* @param t
* @return
*/
public boolean addFirst(T t);
/**
* 获取第一个
* @return
*/
public T getFirst();
/**
* 添加到最后
* @param t
* @return
*/
public boolean addLast(T t);
/**
* 获取最后一个元素
* @return
*/
public T getLast();
/**
* 添加默认添加到最后
* @param t
* @return
*/
public boolean add(T t);
/**
* 添加到指定位置
* @param index 索引
* @param t 数据
* @return
*/
public boolean add(int index, T t);
/**
* 获取指定位置的元素
* @param index 索引
* @return
*/
public T get(int index);
/**
* 移除指定元素
* @param index
* @return
*/
public T remove(int index);
/**
* 移除第一个
* @return
*/
public boolean removeFirst();
/**
* 移除最后一个
* @return
*/
public boolean removeLast();
/**
* 是否包含
* @param object
* @return
*/
public boolean contains(Object object);
/**
* 获取迭代器
* @return
*/
public MyIterator<T> iterator();
}
迭代器接口
package com.ghg.data_structure.link;
public interface MyIterator<T> {
public boolean hasNext();
public T next();
public boolean hasPrevious();
public T previous();
}
实现
package com.ghg.data_structure.link;
import java.util.NoSuchElementException;
public class MyLinkedList<T> implements MyList<T> {
private int size = 0;
private Node<T> first;
private Node<T> last;
private int position = 0;
public MyLinkedList() {
this.first = null;
this.last = null;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public boolean addFirst(T t) {
Node<T> f = first;
Node<T> newNode = new Node<T>(t, null, first);
first = newNode;
if (f == null) {
last = newNode;
} else {
f.pre = newNode;
}
size++;
return true;
}
public T getFirst() {
return first.data;
}
public boolean addLast(T t) {
Node<T> l = last;
Node<T> newNode = new Node<T>(t, l, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
return true;
}
public T getLast() {
return last.data;
}
public boolean add(T t) {
return addLast(t);
}
public boolean add(int index, T t) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
}
if (index == size) {
return addLast(t);
}
Node<T> current = first;
for (int i = 0; i < index; i++) {
current = current.next;
}
Node<T> pre = current.pre;
Node<T> newNode = new Node<T>(t, pre, current);
current.pre = newNode;
/**
* 如果没有前置元素说明是第一个
*/
if (pre == null) {
first = newNode;
} else {
pre.next = newNode;
}
size++;
return true;
}
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
}
Node<T> current = first;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
@Override
public String toString() {
Node<T> current = first;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
sb.append(current);
current = current.next;
}
return sb.toString();
}
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
}
Node<T> current = first;
for (int i = 0; i < index; i++) {
current = current.next;
}
/**
* 获取当前元素的前置也后置元素,将这2个元素相连接
*/
final Node<T> next = current.next;
final Node<T> prev = current.pre;
if (prev == null) {
first = next;
} else {
prev.next = next;
}
if (next == null) {
last = prev;
} else {
next.pre = prev;
}
size--;
return current.data;
}
/**
* 移除第一个
*/
public boolean removeFirst() {
/**
* 获取第一个元素
*/
Node<T> current = first;
/**
* 获取第一个元素的下一个元素
*/
Node<T> next = current.next;
/**
* 赋值
*/
first = next;
/**
* 判断下一个是不是空,如果为空就说明是最后一个,目前只有一个元素
*/
if (next == null) {
last = null;
} else {
// 前置设置为空,因为是第一个了
next.pre = null;
}
size--;
return true;
}
/**
* 移除最后个
*/
public boolean removeLast() {
/**
* 获取最后一个元素
*/
Node<T> current = last;
/**
* 获取最后一个的前一个元素
*/
Node<T> pre = current.pre;
/**
* 赋值
*/
last = pre;
/**
* 判断前置是不是空,如果为空说明第一个为NULL
*/
if (pre == null) {
first = null;
} else {
// 将最后一个元素的,后置设置为空
pre.next = null;
}
size--;
return true;
}
public boolean contains(Object object) {
if (object == null) {
return false;
}
int index = 0;
for (Node<T> current = first; current.next != null; current = current.next) {
if (object.equals(current.data)) {
break;
}
index++;
}
System.out.println("contains index: " + index);
return index > 0;
}
/*
*//**
* 是否有更多
*//*
public boolean hasNext() {
if (position < size) {
return true;
} else {
position = 0;
return false;
}
}
*//**
* 下一个元素
*//*
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return get(position++);
}*/
public class MyInnerIterator<T> implements MyIterator<T> {
private MyLinkedList<T> myLinkedList;
/**
* 游标
*/
private int cursor = 0;
public MyInnerIterator(MyLinkedList<T> linkedList) {
this.myLinkedList = linkedList;
}
public boolean hasNext() {
return cursor<size;
}
public T next() {
return myLinkedList.get(cursor++);
}
public boolean hasPrevious() {
System.out.println("cursor "+cursor);
return cursor>0;
}
public T previous() {
return myLinkedList.get(--cursor);
}
}
/**
* 获取迭代器
*/
public MyIterator<T> iterator() {
return new MyInnerIterator<T>(this);
}
}
测试
package com.ghg.data_structure.link;
public class MyListTest1 {
public static void main(String[] args) {
MyLinkedList<Integer> myLinkedList = new MyLinkedList<Integer>();
myLinkedList.addFirst(3);
myLinkedList.addFirst(5);
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n 获取第一个: " + myLinkedList.getFirst());
System.out.println("\n 获取最后一个: " + myLinkedList.getLast());
myLinkedList.addLast(9);
myLinkedList.addLast(-1);
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n size : " + myLinkedList.size());
myLinkedList.addFirst(67);
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n index : " + myLinkedList.get(1));
myLinkedList.add(45);
myLinkedList.add(-80);
System.out.println("\n 全部: " + myLinkedList.toString());
myLinkedList.add(0, 45);
System.out.println("\n 全部: " + myLinkedList.toString());
myLinkedList.add(8, 43);
System.out.println("\n 全部: " + myLinkedList.toString());
myLinkedList.add(1, 33);
myLinkedList.add(6, 12345);
myLinkedList.add(11, 77);
System.out.println("\n 全部: " + myLinkedList.toString());
myLinkedList.removeFirst();
myLinkedList.removeFirst();
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n size: " + myLinkedList.size());
myLinkedList.removeLast();
myLinkedList.removeLast();
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n size: " + myLinkedList.size());
System.out.println("remove :" + myLinkedList.remove(3));
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n size: " + myLinkedList.size());
System.out.println("\n 全部: " + myLinkedList.toString());
System.out.println("\n contains: " + myLinkedList.contains(3));
System.out.println("get "+myLinkedList.get(6));
/*System.out.println("\n 全部: " + myLinkedList.hasNext());
System.out.println("\n while ");
while(myLinkedList.hasNext()){
System.out.print(myLinkedList.next()+" \t");
}*/
//System.out.println("\n 全部: " + myLinkedList.hasNext());
System.out.println("\n 全部: iterator================ " );
MyIterator<Integer> iterator = myLinkedList.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next()+" \t");
}
MyIterator<Integer> iterator1 = myLinkedList.iterator();
//System.out.println("\n hasnext: "+iterator1.hasNext()+" size "+myLinkedList.size());
System.out.println("\n next : "+iterator1.next());
System.out.println("next : "+iterator1.next());
System.out.println("hasPrevious : "+iterator1.hasPrevious());
System.out.println("previous :"+iterator1.previous());
}
}
image.png
image.png
