package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node<E> next) { this.next = next; } public E getE() { return e; } public void setE(E e) { this.e = e; } }
package 数据结构算法.链表; /* * 定义实现类MyLinkedList * 实现链表的基本功能：增删改查 */ public class MyLinkedList<E> { //声明头节点尾节点 private Node<E> head; private Node<E> last; //链表的大小 private int size; private int modcount; //计算被修改的次数 public MyLinkedList() { head = new Node<E>();//实例化头结点 last = head; } /* *返回单链表中存储的元素总数 */ public int size() { return size; } /* *获取指定索引位置的节点对象 */ public Node<E> get(int index) { if (index < 0 || index > size - 1) return null; Node<E> node = head.getNext();//将头结点的下一个节点赋给Node for (int i = 0; i < index; i++) { node = node.getNext();//获取node的下一个节点 } return node; } /* *获取指定索引位置的数据 */ public E getValue(int index) { if (index < 0 || index > size - 1) return null; Node<E> node = get(index); return node.getE(); } /* *增加元素 */ public void add(E e) { Node<E> node = new Node<E>(e); //以e实例化一个节点 last.setNext(node);//往尾节点后追加节点 last = node;//该节点设为最后一个节点 size++; modcount++; } /* *指定位置插入元素,返回插入的节点数据 */ public E add(int index, E e) { if (index < 0 || index > size - 1) return null; Node<E> node = new Node<E>(e); //实例化一个节点 //找到插入的原节点 Node<E> oldNode = get(index); if (index == 0) {//当索引为0时 head.setNext(node); } else { //找到插入节点的上一个 Node<E> bNode = get(index - 1); bNode.setNext(node); } node.setNext(oldNode); size++; modcount++; return oldNode.getE(); } /* *删除指定的节点e,并返回删除节点的数据 */ public E delete(int index) { if (index < 0 || index > size - 1) return null; if (index == 0) {//当索引为1，令头结点的下一个节点为头结点 Node<E> node = head.getNext(); head.setNext(node.getNext()); } //获取要删除节点的前一个节点 Node<E> bNode = get(index - 1); //获取要删除的节点 Node<E> Node = bNode.getNext(); //获取要删除节点的下一个节点 Node<E> nNode = Node.getNext(); //删除该节点 bNode.setNext(nNode); //清除Node的下一个节点 Node.setNext(null); size--; modcount++; return Node.getE();//返回节点中的数据域 } /* *修改指定位置的数据域并返回修改后的数据 */ public E set(int index, E e) { if (index < 0 || index > size - 1) return null; //获取指定位置的原节点 Node<E> node = get(index); node.setE(e); modcount++; return node.getE(); } }
package 数据结构算法.链表; /* *定义测试类 */ public class MyLinkedListTest { public static void main(String[] args) { MyLinkedList<String> list = new MyLinkedList<>(); //测试add list.add("one"); list.add("two"); list.add("three"); list.add("four"); list.add(0,"newone"); list.add(1,"newtwo"); for (int i = 0; i < list.size(); i++) { System.out.print(list.getValue(i)+" "); } //测试set System.out.println(); list.set(0, "111"); list.set(1, "222"); System.out.println(list.getValue(0) + " " + list.getValue(1)); //测试delete System.out.println(); list.delete(1); for (int i = 0; i < list.size(); i++) { System.out.print(list.getValue(i)+" "); } } }
运行结果如下：
以上就是全部知识点内容，感谢大家对脚本之家的支持。
您可能感兴趣的文章: