/** * @desc: 双链表实现 * @author: 毛会懂 * @create: 2020-12-28 13:58:00 **/ public class MyDoubleLinkList<T> implements MyList<T> { //头指针 private Node head; //尾指针(为了方便向链表末尾插入元素,也为了方便取最后一个元素,会多定义一个字段) private Node last; //元素数量 private Integer count; public MyDoubleLinkList() { //默认指向空节点 head = new Node(null,null,null); last = null; count = 0; } /** * 链表最后添加元素 **/ @Override public void add(T t) { if(count == 0){ Node newNode = new Node(t,head,null); head.next = newNode; last = newNode; }else { Node newNode = new Node(t, last, null); last.next = newNode; last = newNode; } count++; } /** * 指定位置添加元素 **/ @Override public void add(Integer i, T t) { if(i < 0 || i > count){ throw new RuntimeException("位置不正确"); } //添加最后一个元素 if(i == count){ add(t); return; } //找到第i个位置的上一个元素 Node preNode = head; for(int index = 0;index < i;index++){ preNode = preNode.next; } //第i个元素 Node cur = preNode.next; //构造新元素 Node newNode = new Node(t,preNode,cur); preNode.next = newNode; cur.pre = newNode; count++; } /** * 移除指定位置的元素 **/ @Override public T remove(Integer i) { if(i < 0 || i >= count){ throw new RuntimeException("下标超过范围"); } if(count == 0){//没有元素 return null; } Node pre = head; //查询第i个位置的前一个Node for(int index = 0; index <i;index++){ pre = pre.next; } Node cur = pre.next; //当前Node Node next = cur.next; //当前的下一个Node if(next == null){ //移除的是最后一个元素 pre.next = null; cur.pre = null; last = pre; //移除最后一个元素,需要重置last }else{ //不是最后一个元素 pre.next = next; next.pre = pre; } count--; return cur.item; } /** * 更新指定位置的数据 **/ @Override public void update(int i, T t) { if(i < 0 || i >= count){ throw new RuntimeException("下标超过范围"); } Node cur = head; for(int index = 0; index <=i;index++){ cur = cur.next; } cur.item = t; } @Override public T get(int i) { if(i < 0 || i >= count){ throw new RuntimeException("下标超过范围"); } Node cur = head.next; for(int index = 0;index <i;index++){ cur = cur.next; } return cur.item; } /** * 查找元素 **/ @Override public Integer indexOf(T t) { if(count == 0){ return null; } Node cur = head.next; for(int i = 0; i < count;i++){ if(cur.item.equals(t)){ return i; } cur = cur.next; } return null; } @Override public Boolean isEmpty() { return count == 0; } @Override public Integer length() { return count; } @Override public void clean() { head = new Node(null,null,null); last = null; count = 0; } /** * 返回第一个元素 **/ public T getFirst(){ if(isEmpty()){ return null; } return head.next.item; } /** * 返回最后一个元素 **/ public T getLast(){ if(isEmpty()){ return null; } return last.item; } @Override public Iterator<T> iterator() { return new myIterator(); } private class myIterator implements Iterator<T>{ private Node node; public myIterator(){ node = head; } @Override public boolean hasNext() { return node.next != null; } @Override public T next() { T t = node.next.item; node = node.next; return t; } } private class Node{ //元素 private T item; //指向上一个 private Node pre; //指向下一个 private Node next; public Node(T item, Node pre, Node next) { this.item = item; this.pre = pre; this.next = next; } } }
public static void main(String[] args) {
MyList<Integer> myList = new MyDoubleLinkList<>();
myList.add(101);
myList.add(0,100);
System.out.println(myList.length());
myList.forEach(System.out::println);
System.out.println("--------");
//删除
Integer del = myList.remove(1);
System.out.println("删除的元素:" +del);
//更新
myList.update(0,1000);
for (Integer item : myList) {
System.out.println(item);
}
System.out.println("-----------");
myList.add(2000);
myList.add(2,3000);
System.out.println("get到的元素:" + myList.get(1));
System.out.println("查找元素:" + myList.indexOf(1000));//1000的下标为0
System.out.println("第一个元素:" + ((MyDoubleLinkList)myList).getFirst());
System.out.println("最后一个元素:" + ((MyDoubleLinkList)myList).getLast());
myList.clean();
}
本文参考链接:https://www.cnblogs.com/maohuidong/p/14216119.html