数据结构之单链表的增删改查(java版) 逃离我推掉我的手 2022-07-15 04:54 142阅读 0赞 talk is cheap,show you zhe code; /* * 单链表的遍历是从第0个节点开始 沿着next链,一次访问每个节点并且每个节点只能访问一次 * 当头结点head为空时 此链表为空链表 * * 插入操作 * 1空表插入 判断是否为空 插入的节点为该链的头结点 * 2头插入 * Node<T> p = new Node<x,null>;//创建值为x的p结点 * p.next= head; //p.next指向头结点 * head=p; * * 3 */ public class Node<T> { public T data; public Node<T> next; public Node (T data,Node<T> next){ this.data=data; this.next=next; } public Node(){ this(null,null); } public String toString(){ if(data==null) return null; return data.toString(); } } package dataStructure.linkList; /* * 头结点 单链表的存储结构中总是带着头结点的,忽略其数据域 */ public class SingleList<T> { public Node<T> head; public SingleList() { this.head = new Node<T>(); //调用Node的无参构造方法 } public SingleList(T[] values) { this(); // 创建空单链表只有头结点 Node<T> rear = this.head; for (int i = 0; i < values.length; i++) { rear.next = new Node<T>(values[i], null); //为当前结点的next赋值,并将下一结点指向空 即尾插入 rear = rear.next; // 挪到下一结点 } } public boolean isEmpty() { // 头结点 单链表的存储结构中总是带着头结点的,忽略其数据域 // 头结点为之后为空 则链表为空 return this.head.next == null; } public T get(int i) { Node<T> p = this.head.next; for (int j = 0; p != null && j < i; j++) { p = p.next; // 获得后一个结点 } return (i >= 0 && p != null) ? p.data : null; } public void set(int i) { } public int size() { int size=0; Node<T> p = this.head.next; if(this.head.next==null){ //判断第一个结点是否为空 return 0; } do{ p=p.next; size++; }while(p!=null); return size; } /* * @param the loaction of insert * * @param value * 此处采取了容错措施 若i<0则插入最前 若i>size则插入在尾部 */ public void insert(int i, T x) { if (x == null) { throw new NullPointerException("x==null"); } Node<T> front = this.head; for (int j = 0; front.next != null && j < i; j++) { front = front.next; // 遍历到插入处 } front.next = new Node<>(x, front.next); } public void insert(T x){ insert(Integer.MAX_VALUE,x); } public void remove(int i) { Node<T> front = this.head; for (int j = 0; front.next != null && j < i; j++) { front = front.next; // 遍历到i-1处 } if (front.next != null && i >= 0) { front.next = front.next.next; } } public String toString() { String str = this.getClass().getName() + "("; for (Node<T> p = this.head.next; p != null; p = p.next) { str += p.data.toString(); if (p.next != null) { str += ","; } } str += ")"; return str; } public static void main(String[] args) { SingleList<String> testhead = new SingleList<String>(); System.out.println(testhead.head); System.out.println(testhead.head.data); Integer[] valuesnumber = { 1, 5, 3, 5, 6, 86, 89, 4, 5, 35, 7 }; String[] values = { "A", "B", "C", "D" }; SingleList<String> test = new SingleList<String>(values); System.out.println(test.toString()+test.size()); System.out.println("索引为1 的结点值" + test.get(1).toString()); test.insert(-1, "insertlocation"); System.out.println(test.toString()); test.remove(2); test.insert("fd"); System.out.println(test.toString()); SingleList<Integer> test2 = new SingleList<Integer>(valuesnumber); System.out.println(test2.toString()); } }
还没有评论,来说两句吧...