9.双向链表:
9.1双向链表结点的定义：
private class Node1 { //设置结点 T item; //数据域 Node1 next; //指针域Node1 prev; Node1 prev; public Node1(Node1 prev,T item, Node1 next) { this.item = item; this.next = next; this.prev=prev; } }//调用节点类
9.2双向链表添加末尾元素:
public void add(T t){ //先把插入点的prev指针指向前一个last Node1 prev=last; //获取插入的元素 Node1 node1=new Node1(prev,t,null); //然后把插入点前的next指针指向插入点的结点 if(prev==null){ //假如说插入点的前一个点是null first=node1; } else { prev.next = node1; } //将last指向新插入的元素 last=node1; //进行++操作 this.size++; }
9.3获取双向链表的结点:
public Node1 getNode(int idex){ int mid=size/2; //获取中间值 if(idex<mid){ //如果小于，那么就从第一个节点开始遍历 Node1 x=first; for(int i=0;i<idex;i++){ x=x.next; } return x; }else{ //否则，那么就从最后i一个结点遍历 Node1 x=last; for(int i=size-1;i>idex;i--){ //这里可不能少 x=x.prev; } return x; } }
9.4向指定位置添加元素
public void add(int idex,T t){ if(idex==size){//假如说是最后一个位置 add(t); }else{ //获取需要插入元素的结点 Node1 node1=new Node1(null,t,null); //获取被插入点的结点 Node1 current=getNode(idex); if(current==null){ first=node1; }else { //获取被插入点前的结点 Node1 befor = current.prev; //插入点prev指向前结点 node1.prev=befor; //插入点next指向后一个结点 node1.next=current; //后一个结点prev指向插入点 current.prev=node1; //假如说是第一个位置 if(befor==null){ first=node1; } else { befor.next = node1; } } this.size++; } }
9.5删除元素
public void remove(int idex) { //设置删除点 Node1 current = getNode(idex); //删除点前面 Node1 before = current.prev; //删除点后面 Node1 after = current.next; if(before==null){ //假如说删除头部 first=after; }else{ before.next = after;} if (after == null) { //假如说删除末尾 last = before; } else { after.prev = before; } this.size--; }
9.双向链表的全部用法
类方法:
import org.jetbrains.annotations.NotNull; public class LinkedList<T> { Node1 first; //指向第一个结点 Node1 last; //指向最后一个结点 int size; //链表长度 public LinkedList() { //初始化链表 this.size = 0; } //获取指定位置的结点 public Node1 getNode(int idex) { int mid = size / 2; //获取中间值 if (idex < mid) { //如果小于，那么就从第一个节点开始遍历 Node1 x = first; for (int i = 0; i < idex; i++) { x = x.next; } return x; } else { //否则，那么就从最后i一个结点遍历 Node1 x = last; for (int i = size - 1; i > idex; i--) { //这里可不能少 x = x.prev; } return x; } } //在指定位置添加元素 public void add(int idex,T t){ if(idex==size){//假如说是最后一个位置 add(t); }else{ //获取需要插入元素的结点 Node1 node1=new Node1(null,t,null); //获取被插入点的结点 Node1 current=getNode(idex); if(current==null){ first=node1; }else { //获取被插入点前的结点 Node1 befor = current.prev; //插入点prev指向前结点 node1.prev=befor; //插入点next指向后一个结点 node1.next=current; //后一个结点prev指向插入点 current.prev=node1; //假如说是第一个位置 if(befor==null){ first=node1; } else { befor.next = node1; } } this.size++; } } //获取指定位置的元素 public T get(int idex) { return getNode(idex).item; } //在末尾元素进行添加 public void add(T t) { //先把插入点的prev指针指向前一个last Node1 prev = last; //获取插入的元素 Node1 node1 = new Node1(prev, t, null); //然后把插入点前的next指针指向插入点的结点 if (prev == null) { //假如说插入点的前一个点是null first = node1; } else { prev.next = node1; } //将last指向新插入的元素 last = node1; //进行++操作 this.size++; } //在指定位置进行删除 public void remove(int idex) { //设置删除点 Node1 current = getNode(idex); //删除点前面 Node1 before = current.prev; //删除点后面 Node1 after = current.next; if(before==null){ //假如说删除头部 first=after; }else{ before.next = after;} if (after == null) { //假如说删除末尾 last = before; } else { after.prev = before; } this.size--; } //获取当前链表的长度 public int size(){ return size; } private class Node1 { //设置结点 T item; //数据域 Node1 next; //指针域Node1 prev; Node1 prev; public Node1(Node1 prev,T item, Node1 next) { this.item = item; this.next = next; this.prev=prev; } }//调用节点类 }
主方法:
import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs) { LinkedList<String> s=new LinkedList<>(); s.add("aa"); s.add("bb"); s.add("cc"); s.add("dd"); s.add("ee"); s.remove(4); for(int i=0;i<s.size();i++){ System.out.println(s.get(i)); } } }
