数据结构 -- 双向链表 linkedList 手写

双向链表 linkedList

package list;
public class LinkedList<E> {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
public void
add(E e){
linkedLast(e);
size++;
}
private void linkedLast(E e) {
// TODO Auto-generated method stub
Node<E> newNode = new Node<E>(last, e, null);
System.out.println("e=="+e);
//先保存起来last
Node<E> l = last;
//将最后一个last指向新元素
last = newNode;
//当last为空时 first指向元素 否则 将最后一个元素的next 指向新节点
if (l ==null) {
first = newNode;
}else{
l.next = newNode;
}
}
/**
* 在任意位置添加元素
* @param index
* @param e
*/
public void
add(int index,E e){
if (index<0 || index >size || e == null) {
return;
}
//当是在尾部添加元素时
if (index == size) {
linkedLast(e);
}else{
Node<E> p = node(index);
//当时在头部添加元素时
if (index == 0) {
Node<E> newNode = new Node<E>(null, e, p);
p.prev = newNode;
first = newNode;
}else{
//找到index节点的p的prev节点
Node<E> pp = p.prev;
//创建要添加的e的节点对象	并将它的前节点和后节点设置
Node<E> newNode = new Node<E>(pp, e, p);
//将前一个节点的下一个节点指向新节点
pp.next = newNode;
//将原来p节点的上一个节点设置给新节点
p.prev = newNode;
}
}
size++;
}
public void remove(int index) {
Node<E> target = node(index);
unlinked(target);
size --;
}
private void unlinked(Node<E> p){
//当是顶点节点时
if (p.prev == null) {
first = p.next;
}else{
p.prev.next = p.next;
}
//当时尾部节点时
if (p.next == null) {
last = p.prev;
}else{
p.next.prev = p.prev;
}
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
public E get(int index) {
if (index<0 || index >size) {
return null;
}
return node(index).item;
}
private Node<E> node(int index) {
// TODO Auto-generated method stub
//优化算法
if (index < (size>>1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}else{
Node<E> node1 = last;
for (int i = size -1; i > index; i--) {
node1 = node1.prev;
}
return node1;
}
}
}
测试代码
package list;
public class TestMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("aaaa");
linkedList.add("bbbb");
linkedList.add("cccc");
linkedList.add(0,"dddd");
linkedList.add(1,"eeee");
for (int i = 0; i < linkedList.size; i++) {
System.out.print(linkedList.get(i)+"--"+linkedList.get(i+1)+"
");
}
System.out.println();
linkedList.remove(0);
for (int i = 0; i < linkedList.size; i++) {
System.out.print(linkedList.get(i)+"--"+linkedList.get(i+1)+"
");
}
}
}

最后

以上就是勤奋台灯为你收集整理的数据结构 -- 双向链表 linkedList 手写的全部内容，希望文章能够帮你解决数据结构 -- 双向链表 linkedList 手写所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。