一：LinkedList
1.定义head节点，用于存放头节点信息
private Node head;
2.定义size，用于表示链表长度
private Integer size = 0;
3.定义Node对象，用于表示某个节点的所有属性
class Node {
//存放数据
E data;
//前继节点
Node next;
//后继节点
Node prev;
//构造器
public Node(E e){
data = e;
}
}
- Node用于描述表中的一个节点
- 其中，data用于存放于元素
- next是存放前继节点
- prev用于存放指向其后继节点
4.将元素追加到链表的末尾
public boolean add(E e){
//将元素封装成一个节点
Node node = new Node(e);
//如果链表为空，则新节点就是头节点
if(head == null){
head = node;
head.next = node;
head.prev = node;
//链表的长度加1
size ++;
return true;
}
//找到末尾节点地址
Node last = head.prev;
//将新节点添加到未节点后面
last.next = node;
node.next = head;
head.prev = node;
node.prev = last;
//链表的长度加1
size ++;
return true;
}
5.将元素插入到指定下标处
public void add(int index,E e){
if( index < 0 || index > size ){
throw new IndexOutOfBoundsException("数组下标越界异常");
}
if(index == size){
add(e);
}
//将元素封装成一个节点
Node node = new Node(e);
Node next = getNode(index);
Node prev = next.prev;
next.prev = node;
node.prev = prev;
prev.next = node;
node.next = next;
if(index == 0){
head = node;
}
size ++;
}
6.返回指定位置的节点
private Node getNode(Integer index) {
//从头结点开始遍历
Node node = this.head;
//此时可以用移位运算
//为了提升性能，可以通过比较index与链表的长度的一半来决定是向前遍历还是向后遍历
if (index < size >>1){
for (int i = 0; i < index; i++) {
node = node.next;
}
} else {
for (int i = size; i > index ; i--) {
node = node.prev;
}
}
return node;
}
7.移除指定位置处的元素
public E remove(Integer index){
if(index < 0||index >=size){
throw new IndexOutOfBoundsException("数组下标越界异常");
}
//如果链表只有一个元素,则删除该节点以后，需要将head设置为null,并返回删除的元素
if (size == 1) {
E data = head.data;
head = null;
size --;
return data;
}
//找到要删除的节点
Node node = this.getNode(index);
//找到该节点的前驱节点和后继节点
Node next = node.next;
Node prev = node.prev;
//将该节点删除(其实就是在prev和next之间建立引用关系)
prev.next = next;
next.prev = prev;
//如果被删除的元素为头节点,则其下一个节点为头节点
if(index == 0){
head = next;
}
//链表长度减1
size--;
return node.data;
}
8.重写toString方法
@Override
public String toString(){
if(head == null){
return "[]";
}
StringBuilder stringBuilder = new StringBuilder("[");
stringBuilder.append(head.data);
Node node = head.next;
while(node.next != head){
stringBuilder.append("," + node.data);
//继续查找下个节点
node = node.next;
}
return stringBuilder.append("]").toString();
}
9.源码在此
package com.sysg.list;
public class LinkedList {
private Node head;
private Integer size = 0;
class Node {
//存放数据
E data;
//前继节点
Node next;
//后继节点
Node prev;
//构造器
public Node(E e){
data = e;
}
}
public boolean add(E e){
//将元素封装成一个节点
Node node = new Node(e);
//如果链表为空，则新节点就是头节点
if(head == null){
head = node;
head.next = node;
head.prev = node;
//链表的长度加1
size ++;
return true;
}
//找到末尾节点地址
Node last = head.prev;
//将新节点添加到未节点后面
last.next = node;
node.next = head;
head.prev = node;
node.prev = last;
//链表的长度加1
size ++;
return true;
}
public void add(int index,E e){
if( index < 0 || index > size ){
throw new IndexOutOfBoundsException("数组下标越界异常");
}
if(index == size){
add(e);
}
//将元素封装成一个节点
Node node = new Node(e);
Node next = getNode(index);
Node prev = next.prev;
next.prev = node;
node.prev = prev;
prev.next = node;
node.next = next;
if(index == 0){
head = node;
}
size ++;
}
public E get(Integer index){
if(index < 0 || index >= size){
throw new IndexOutOfBoundsException("数组下标越界异常");
}
Node node = getNode(index);
//返回该节点存放的数据
return node.data;
}
public E remove(Integer index){
if(index < 0||index >=size){
throw new IndexOutOfBoundsException("数组下标越界异常");
}
//如果链表只有一个元素,则删除该节点以后，需要将head设置为null,并返回删除的元素
if (size == 1) {
E data = head.data;
head = null;
size --;
return data;
}
//找到要删除的节点
Node node = this.getNode(index);
//找到该节点的前驱节点和后继节点
Node next = node.next;
Node prev = node.prev;
//将该节点删除(其实就是在prev和next之间建立引用关系)
prev.next = next;
next.prev = prev;
//如果被删除的元素为头节点,则其下一个节点为头节点
if(index == 0){
head = next;
}
//链表长度减1
size--;
return node.data;
}
public int size(){
return size;
}
@Override
public String toString(){
if(head == null){
return "[]";
}
StringBuilder stringBuilder = new StringBuilder("[");
stringBuilder.append(head.data);
Node node = head.next;
while(node.next != head){
stringBuilder.append("," + node.data);
//继续查找下个节点
node = node.next;
}
return stringBuilder.append("]").toString();
}
private Node getNode(Integer index) {
//从头结点开始遍历
Node node = this.head;
//此时可以用移位运算
//为了提升性能，可以通过比较index与链表的长度的一半来决定是向前遍历还是向后遍历
if (index < size >>1){
for (int i = 0; i < index; i++) {
node = node.next;
}
} else {
for (int i = size; i > index ; i--) {
node = node.prev;
}
}
return node;
}
}
