Skip to main content
 首页 » 编程设计

java算法之自定义线性结构-双链表方式

2022年07月18日82grandyang
/** 
 * @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