JAVA 双向链表

实现代码

package demo0110.algorithm.linear;import java.util.Iterator;/*** @Author: 从南到北* @Date: 2022/01/10/14:43*/
public class TowWayLinkList<T> implements Iterable<T>{//初始化头节点private Node head;private Node last;private int N;//初始化public TowWayLinkList(){last = null;head = new Node(null,null,null);N = 0;}//清空链表public void clear(){last = null;head.next = last;head.pre = null;head.item = null;N = 0;}//获取链表长度public int length(){return N;}//判断链表是否为空public boolean isEmpty(){return N==0;}//插入元素t,即在尾部添加元素public void insert(T t){if (last == null){last = new Node(t,head,null);head.next = last;}else{Node oldLast = last;Node node = new Node(t,oldLast,null);oldLast.next=node;last = node;}N++;}//在指定位置i处插入元素tpublic void insert(int i,T t){if (i>=N||i<0){throw new RuntimeException("位置不合法");}//找到位置i的前一个节点Node pre = head;for (int index = 0;index<i;index++){pre = pre.next;}//当前节点Node cur = pre.next;Node newNode = new Node(t,pre,cur);cur.pre = newNode;pre.next = newNode;N++;}//获取指定位置i处的元素public T get(int i){if (i<0||i>=N){throw new RuntimeException("位置不合法");}//寻找当前i节点Node curr = head.next;for (int index = 0;index<i;index++){curr = curr.next;}return curr.item;}//找到元素t在链表中第一次出现的位置public int indexOf(T t){Node n = head;for (int i =0;n.next!=null;i++){n=n.next;if (n.item.equals(t)){return i;}}return -1;}//删除位置i处的元素，并返回该元素public T remove(int i){if (i<0||i>=N){throw new RuntimeException("位置不合法");}//找到前一个元素Node pre = head;for (int index = 0;index<i;index++){pre = pre.next;}Node curr = pre.next;//i位置的下一个元素Node curr_next = curr.next;pre.next = curr_next;curr_next.pre=pre;N--;return curr.item;}//获取第一个元素public T getFirst(){if (isEmpty()){return null;}return head.next.item;}//获取最后一个元素public T getLast(){if (isEmpty()){return null;}return last.item;}@Overridepublic Iterator<T> iterator() {return new TIterator();}private class TIterator implements Iterator{private Node n = head;@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next() {n = n.next;return n.item;}}//节点类private class Node{public Node pre;public Node next;public T item;public Node(T item,Node pre,Node next){this.item = item;this.pre = pre;this.next = next;}}}

测试代码

package demo0110.algorithm.test;import demo0110.algorithm.linear.TowWayLinkList;/*** @Author: 从南到北* @Date: 2022/01/10/20:46*/
public class TowWayLinkListTest {public static void main(String[] args) {TowWayLinkList<String> list = new TowWayLinkList<>();list.insert("c");list.insert("d");list.insert("e");list.insert("f");list.insert(0,"a");list.insert(1,"b");for (String str:list){System.out.println(str);}System.out.println("----------------");System.out.println(list.get(2));System.out.println(list.remove(3));System.out.println(list.length());System.out.println(list.getFirst());System.out.println(list.getLast());}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！